摘 要

近些年来，由于人们生活水平的提升，出行的要求也随之提高，我国交通压力越来越重，部分地区道路堵塞问题严重。交通部门针对这些问题也是想了很多办法、采取了一些措施，但是在某些地区效果不是特别显著。如果想从根本上解决问题，就必须采取合理的交通方式和运营方法，并且可以让人们接受、满意。本文提出了一种基于已知候选站点的微型巴士的运营模式，可以很好的解决末端交通困难的问题。

本文提出的新型微巴模式是指根据乘客的需求对乘客进行分组，为位置较近的乘客建立与各乘客距离合适的站点，然后对微巴行驶路线进行规划，找到最优路线。它的优势在于能够满足乘客的乘车时间需求、减少客车的空跑行程。本文首先根据乘客的乘车需求，对乘客的地理位置和候车时间进行统计整理，设置临时站点位置以及候车站点时间窗。然后对微巴的行驶路径进行规划并将其归为带时间窗的车辆路径问题(VRPTW)，利用求解VRPTW的方法找到最优路径。

本文通过构建惩罚函数的方法，综合考虑微巴运行过程中的时间约束、客户满意度以及车辆行驶费用等因素，建立了带有惩罚函数的VRPTW改进模型，利用MATLAB中的遗传算法进行编程，编写可以找到最优解的程序，找出满足条件的最优解。

最后，通过算例对算法进行实现、验证，根据算例给出的条件找到最优路径。本文的研究证明了课题的可行性，也证明了运用遗传算法可以有效地找到VRPTW的最优解。

关键词：候选站点；VRPTW；MATLAB；遗传算法

Abstract

In recent years, people‘s requirement in transportation have increased due to the improvement of their living standards. China's traffic pressure is increasingly severe and there is a growing number of traffic congestion in many areas. The transportation department has tried amount of ways to tackle these problems and taken a lot of measures. But the effect is not particularly significant in some regions. If we want to resolve the issue fundamentally, we must adopt reasonable methods of travelling and operating which can be accepted by the mass. This article presents an operating model of micro bus based on known candidate sites, which can solve the difficulty of the terminal traffic.

The new type of micro-bus model proposed by this paper refers to dividing passengers into groups according to the needs of them, establishing a suitable site for each passenger, and then planning the driving routes to find the optimal one. Its advantage is to be able to meet the needs of passenger's travel time and reduce the empty running journey of bus. This article suggests that the first step is to collect statistics about the passenger's location and waiting time on the basis of their needs of the car. Then establish the temporary site location and time window of waiting site. Next, plan the routing path of the micro bus and classify it into the vehicle routing problem with time window (VRPTW). The optimal path would be found by solving VRPTW finally.

The VRPTW improving model with penalty function is established In this thesis by constructing the penalty function method, considering various factors including time constraint, customer satisfaction, vehicle driving cost, etc comprehensively. We can write program to find the optimal solution with the genetic algorithm in MATLAB and find the optimal solution which meet the criteria.

Finally, implement and verify the algorithm through example and find the optimal path through the conditions given by the example. The studies in this paper prove the feasibility of this project and that the genetic algorithm can find the optimal solution of VRPTW effectively.

Key words: candidate site, VRPTW, MATLAB, genetic algorithm

目录

摘要 I

Abstract II

第一章 绪论 1

1.1研究的背景和意义 1

1.2国内外研究现状 2

1.2.1国内研究现状 2

1.2.2国外研究现状 3

1.3本文主要研究的内容 4

第二章 车辆路径问题概述 6

2.1旅行商问题(TSP) 6

2.2车辆路径问题 7

2.2.1车辆路径问题的描述 7

2.3带时间窗的车辆路径问题(VRPTW) 8

2.3.1时间窗的概念及描述 8

2.3.2时间窗的分类 9

2.4本章小结 11

第三章 VRPTW模型构建及算法设计 12

3.1 VRPTW模型构建 12

3.1.1 问题描述 12

3.1.2模型假设 13

3.1.3时间窗的界定 14

3.1.4惩罚函数的建立 14

3.1.5参变量定义 15

3.1.6VRPTW的优化数学模型 15

3.2算法设计 16

3.2.1遗传算法基本工作流程 18

3.2.2遗传算法设计 18

3.3本章小结 19

第四章 算例分析 20

4.1算例说明 20

4.2分析问题 21

4.3试验参数设定 22

4.4算法实现步骤 23

4.5实验结果分析 25

4.6本章小结 27

第五章 环境影响及经济性分析 28

5.1环境影响分析 28

5.1.1环境影响因素分析 28

5.1.2环境影响分析结论 28

5.2经济性分析 28

5.2.1经济性因素分析 28

5.2.2经济性分析结论 29

第六章 总结与展望 30

6.1全文总结 30

6.2研究展望 30

参考文献 32

致谢 34

第一章 绪论

1.1研究的背景和意义

在当今社会，经济迅速发展、获取效益的途径越来越多，物流已经成为“第三利润源泉”^[1]，它成为了一个重要课题，在经济发展中发挥着越来越重要的作用。配送作为作为物流中最基本、最重要的部分，渐渐地受到了人们的重视。在整个物流中，配送成本所占比例也日益增加。因此，通过减少配送资金的方式解决物流成本高的问题显得尤其重要。综上所述，选择经济、有效地配送路径，减少行车费用支出成为了大多数企业增加企业效益的重要途径。

车辆路径问题(Vehicle Routing Problem,缩写为VRP)^[2]是物流中的关键步骤，它所占物流成本中的很大部分，是物流过程中的首要问题。VRP通常指在满足一些指定的要求下(如客户需求量、客户时间要求、车辆容量限制等)，配送中心通过规划合适的车辆路径、选取适当的车辆数量，依次通过一组已知的客户点，找到最优的行车方案，达到预先定下的目标(如行车距离最短、运输成本最低等)。在当今低碳环保的要求下，VRP的研究显得格外的重要。目前，我国大多数物流还停留在非技术手段的简单物流，对物流配送中的VRP技术还没有掌握完善。VRP作为物流配送目前首先要考虑的问题,是物流业健康、快速发展的重中之重。在满足约束条件下规划合适的运输路线不但可以增加公司的利润还能提高企业竞争力和工作效率。另一方面，它能够减轻交通压力、缩短不必要的运输路径，从而达到减轻环境污染、节约能源的效果。实现节能、高效、环境全面优化，促进交通发展、解决交通问题。

随着社会观念不断发展，人们对工作效率、企业规划愈加重视，带时间窗的配送形式应运而生，满足客户允许的时间进行配送已经成为VRP的一个新的目标。带时间窗的车辆路径问题(Vehicle Routing Problem With Time Windows,简称VRPTW)^[3]成为了物流领域中重点研究问题。带时间窗的车辆路径问题是指在一般车辆路径问题中加入了客户的时间窗要求，在满足时间窗的要求下进行路径规划，使路径最短或者运输费用最低。VRPTW的出现符合现代社会的时代要求，对路径规划加以时间窗的约束可以提高配送的效率以及企业生产的效率，使企业生产获得连续、有序的生产保障。