1.1 研究背景

随着经济社会的不断发展和外国优秀企业先进管理理念的逐步引入，物流成本的控制与管理受到越来越广泛的重视。在通过对设备的更新以及提高自动化水平难以大幅提高利润的今天，通过降低物流成本来提高市场竞争力就成为了发达国家的重视之处。

物流成本的降低不仅可以为企业增加利润，而且可以降低商品价格，从而带动消费者的购买能力，最终促进国民经济的发展。而我国企业的物流成本远高于欧美国家，因此，在我国大力发展现代物流，不仅可以提高国民经济的质量和效益，使资源得到合理优化的配置，而且可以提高企业的产品竞争力和顾客服务水平，最终提高我国的经济发展水平，促进与世界经济的逐步融合。

车辆路径问题 (VehicleRouting Problem, VRP)是降低运输成本的关键问题。其产生于现实的公路交通运输领域，并在国防、生物、计算机应用、通讯、生产等领域得到了广泛的应用。但VRP 发展至今，在问题规模较大时仍然很难得到问题的精确解。因此，探讨如何经过少量的计算，得到一个相对满意的解，已成为现阶段相关学者研究的重点。

1.2 研究目的及意义

本文的研究目标主要是在对考虑容量约束的车辆路径问题（CapacitatedVehicle Routing Problem, CVRP）分析和建模的基础上，通过搜索策略的改进以及与其他各种求解算法的综合建立起一种新的改进遗传算法。然后，对该算法进行数据实验，最后，以该算法为核心开发一款相应的配送路径优化方案，使得求解CVRP的速度更快、效果更好，增强现实中物流配送活动的实用性。

就现实意义而言，由于在CVRP中，一个中心仓库需要给n个客户提供服务，其目的是找出一种运输成本最小的路径方式，是一个NP难问题。因此合理的解决车辆路径规划问题和车辆配载问题可以降低车辆空驶率、节约车辆资源、降低运输成本、提高配送响应速度和物流配送的效率，对于降低物流配送成本有着重要的意义，同时对电子商务和物流配送发展也有一定的理论意义与应用价值。

1.3国内外研究现状

以下将从车辆路径问题的研究概况以及元启发式算法的研究概况两方面综述国内外研究现状：

1.3.1车辆路径问题的研究概况

1959年，Dantzig和Ramser^[1]首先提出了车辆路径问题，他们在文献中描述中心仓库通过卡车将汽油运送到各个加油站，在满足各加油站需求的情况下，使车队行驶的总里程最短，对该问题进行了进行数学建模，并提出了相应的解决方法。

在基本车辆路线问题的基础上，车辆路线问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW）、考虑同时取送货的问题( Vehicle RoutingProblem with Simultaneous Pickup and Delivery ,VRPSPD)、有能力约束的车辆路径调度（Capacitated Vehicle Routing Problem, CVRP）、随机需求车辆路线问题（vehicle routing problem with stochastic demand，VRPSD）等。

(1)时窗限制车辆路线问题

时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW）是车辆路径规划问题中一个重要的分支，由 Solomon^[2]于1987年首次将时间窗约束条件加入其中，因为实际配送中顾客有具体的服务时间窗限制，因此为了进一步提高服务质量，迎合顾客需求，企业往往会考虑顾客的时间窗需求。

对于VRPTW问题，主要的研究方法有两类。一类是精确算法，另一类是启发式算法。精确算法大致可分为三类：列生成算法、基于拉格朗日松弛的算法以及动态规划，主要应用于小规模问题的计算和求解，可以求得精确解。针对精确算法求解大规模问题的高昂的计算成本和不尽如人意的表现，取得较好效果的是启发式算法。其中包括模拟退火算法、遗传算法、禁忌搜索算法和粒子群算法，这些算法均可以在一定范围内得到其中的满意解。

针对该问题，Holland首先采用遗传算法（GA）编码解决VRPTW 问题，并取得了显著成果。

(2)考虑同时取送货的问题

考虑同时取送货的问题( Vehicle Routing Problem with Simultaneous Pickup and Delivery,VRPSPD)是考虑到中心仓库的车辆不仅需要为顾客提供货物配送服务，而且顾客同时也有取货的需求，需要将货物运回中心仓库，且两者不可以独立进行服务

针对该问题，北京交通大学的王超^[3]提出一种基于禁忌规则的模拟退火算法进行求解，并在同时提出了一种并行模拟退火算法来求解考虑带时间窗和同时取送货的车辆路径问题（VRPSPDTW）。

该问题的难点在于车辆的装载量难以控制，易超过车辆的容量。因此在顾客的需求已知的情况下，应根据车辆的剩余装载能力来定义插入准则。

(3)有能力约束的车辆路径调度

有能力约束的车辆路径调度（Capacitated Vehicle Routing Problem, CVRP），此模型是车辆路径问题的基本模型。

CVRP的目的是找出一种总的运货成本最小的运输方式，并且满足以下限制:

① 每个顾客只接受1次服务，只被一辆车服务;

② 每一辆车的都是从配送中心出发，并且最后返回配送中心;

③ 每一辆车均有容量限制。

此模型研究的时间最长,取得的成果最多,大量的精确算法,启发式算法用于求解此问题,其他模型的各种求解算法也大多衍生于此。

南京农业大学的李林^[4]针对二维装箱约束（即考虑体积约束）着重进行相关研究，并得到优化解决方案。王超^[5]等人则提出了面向不同目标偏好的车载能力约束车辆路径问题的多目标优化模型( MOCVRPFDTP) ，并设计了算法求解。Sener Akpinar^[6]应用混合大邻域搜索算法对CVRP进行了研究求解。

(4)随机需求车辆路线问题

随机需求车辆路线问题（vehicle routing problem with stochastic demand，VRPSD）该问题是VRP的一个重要的子分支,因为其贴近现实,因此成为物流管理领域研究的热点。如何在顾客需求随机的情况下,合理安排车辆行驶路径,以实现运输时间最短、成本最低等目标,是该问题研究的难点。

韩娟娟^[7]研究了决策者风险偏好对随 VRPSD 求解的影响并确定了使优化目标最小的决策者风险偏好值，设计了高效的混合遗传算法对 VRPSD 进行求解，为求解VRPSD 和发展遗传混合算法提供了有用的价值。

1.3.2元启发式算法的研究概况

元启发式算法（ MetaHeuristic Algorigthm ）是启发式算法的改进，它是随机算法与局部搜索算法相结合的产物。

元启发式算法是相对于最优化算法提出来的，一个问题的最优化算法可以求得该问题的最优解，而元启发式算法是一个基于直观或经验构造的算法，它可以在可接受的花费(指计算时间和空间)下给出问题的一个可行解，并且该可行解与最优解的偏离程度不一定可以事先预计。

元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法等。

(1)禁忌搜索算法

禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，该方法最早是由Glover在1986年提出的。它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立，同时通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。

在国内，李阳^[8]等人将禁忌搜索算法和变邻域搜索算法相结合，基于先预优化后重调度的思想，提出一种新的两阶段变邻域禁忌搜索算法（VNTS）对模糊需求车辆路径问题进行求解，点重调度策略调整效果较佳。

(2)模拟退火算法

模拟退火(simulated annealing)算法来源于固体退火原理，是一种基于概率的算法，最初是由Metropolis在1953年提出的，其基本思想是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比，试图通过模拟高温物体退火过程来找到优化问题的全局最优解或者近似最优解。

大量的模拟实验表明，模拟退火算法在求解这些问题时能产生令人满意的近似最优解，而且所用的时间也不是很长。

(3)遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法该算法(Genetic Algorithm)是由美国Michigan大学的John Holland教授于1975年首次提出的。

他的基本方法是：首先参照二进制编码创造初代种群，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用精确算法很难求出最优解或需要较长时间及成本。对这类复杂的问题，求得一个满意解来当作最优解显得尤为必要，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。

近年来，针对遗传算法的研究是研究热点之一，例如甘宝 ^[9] 等人通过改进的遗传算法不断地调整染色体的交叉和变异概率进行优化，最终得到了物流中心车辆安排的合理方案。 Habibeh Nazif, Lai Soon Lee.^[10]等人也用遗传算法对有容量约束的车辆路径问题进行了研究分析。

(4)蚁群算法

蚁群算法(ant colony optimization, ACO)是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

该算法的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

近年来涌现了很多ASO应用于调度问题的研究。W.Y. Szeto^[11]在两组标准基准实例上评估增强启发式的性能，并与原始的人工蜂群算法进行比较。王书勤^[12]在论文中针对有容量约束的车辆路径问题以及蚁群算法的本身，对蚁群算法在现有基础上进行了改进，提出一种新的改进蚁群算法，实例仿真证明该算法能够较好地解决规模不大的有容量约束的车辆路径问题。而陈亮^[13]等人针对基本蚁群算法在求解CVRP时收敛速度慢、求解质量不高的缺点，引入基于DT策略的候选列表，以提高构建路径的质量提出了一种改进的蚁群系统算法求解CVRP。

(5)粒子群优化

粒子群优化(particle swarm optimization, PSO )是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法，该算法是由Eberhart博士和Kennedy博士发明。

PSO是一种基于群体智能的全局随机寻优算法，它模仿鸟类的觅食行为，将问题的搜索空间类比于鸟类的飞行空间，将每只鸟抽象成为一个微粒，用以表征问题的一个候选解，所需要寻找的最优解等同于要寻找的食物。算法为每个微粒给定位置和速度，每个微粒通过更新速度来更新其自身的位置。通过迭代搜索，种群可以不断地找到更好的微粒位置，从而得到优化问题的较优解。

1.3.3总结分析

综合以上所述可知，关于车辆路径问题的研究国外开始的时间相较于国内早一些。国内外学者构建模型时选择的目标有最短总行驶距离、最小配送成本、最少碳排放量、顾客满意度最大等，主要以单目标问题为主。约束条件涉及的比较全面，包括时间窗约束、车辆装载量约束、车辆服务距离和时间上限约束、路径约束等。现有研究大多数情况下不对车辆加以区分，并且车辆多假设为匀速行驶。构建模型时，考虑的限制因素越多，便更为贴近实际场景，但求解难度也会随之增加。

现在VRP的研究阶段处于基于智能优化算法的车辆路径问题的研究阶段， VRP的算法研究已经成了人工智能算法研究方面的一个研究热点问题，而且很多的很复杂的 VRP 都期待找到一种理想的算法来解决。国内外学者大多都致力于改进已有的算法，或将已有的几种算法相结合，不断优化完善算法来寻求该问题的更优解。

针对上述情况，区别于传统的有容量约束的车辆路径问题研究，本文的创新点主要有以下几点：

2.1研究的基本内容

第一部分：介绍选题背景及研究意义，阐述有容量约束的车辆路径优化问题研究现状，主要包括车辆路径问题的研究概况以及元启发式算法的研究概况，并分析当前研究不足之处；

第二部分：从运筹学、应用数学的角度阐述车辆路径问题的定义及其数学模型，同时介绍VRP 问题的特征并对其进行分类，以及现阶段VRP 问题的相关求解方法；

第三部分：重点介绍多目标遗传算法，主要包括多目标最优化及Pareto相关概念和多目标遗传算法的研究概况；

第四部分：针对遗传算法自身存在的缺陷，结合其他算法对其进行优化改进，设计一种多目标遗传算法的优化算法；

第五部分：结合一个车辆路径规划案例，采用MATLAB对建立基于多目标遗传算法的优化算法求解车辆路径问题的数学模型进行编程，分析和评价优化前后效果。

2.2研究拟采用的技术方案及措施

（1）文献分析法

主要车辆路径规划模型和相关研究算法方面的文献进行收集、鉴别和整理，归纳总结，形成对其的一个全面认识；

（2）数学建模法

数学建模方法是运用用符号、函数关系将评价目标和内容系统规定下来，并把互相间的变化关系通过数学公式表达出来。本文即是将有容量约束的车辆路径规划模型用数学符号表示出来，由此求出最优解；

（3）多目标遗传算法

本文中运用到多目标遗传算法对车辆路径问题进行研究，就是研究在满足配送车辆不超载等前提下，使车辆容量利用率尽可能高以及总成本尽可能低，运用该算法得到一定范围内的最优解；

（4）算法设计与改进

针对遗传算法自身存在的缺陷，结合其他算法对其进行优化改进，设计一种多目标遗传算法的优化算法；

（5）优化分析法

本文中利用MATLAB软件对所建立出来的模型进行优化分析，求出最优解。

具体技术路线图如下：

周次

目标任务

1-3

明确任务书内容，查阅相关文献，撰写开题报告；

4

提交开题报告及核心文献；

5

翻译外文文献；

6-7

学习MATLAB及相关算法；

8

建立论文的相关模型；

9

撰写论文初稿；

10-13

修改论文，完成最终稿，装订打印；

14-16

准备答辩材料，完成毕业论文答辩。

[1]Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. ManagementScience,1959,6(1):80-91.

[2]Solomon M M. Algorithms for the Vehicle Routing and SchedulingProblems with Time Window Constraints[M]. INFORMS, 1987.

[3]王超. 配送企业车辆路径问题模型与算法研究[D].北京交通大学,2015.

[4]李林. 考虑装箱约束的集散货物路径问题研究[D].南京农业大学,2013.

[5]王超,金淳,韩庆平.面向不同目标偏好的CVRP多目标模型及其求解方法[J].计算机应用研究,2016,33(08):2270-2274.

[6]Sener Akpinar. Hybrid large neighbourhood search algorithm forcapacitated vehicle routing problem [J]. Expert Systems with Applications.Volume 61, 1 November 2016, Pages 28-38

[7]韩娟娟. 随机需求车辆路径问题的混合遗传算法研究[D].辽宁师范大学,2016.

[8]李阳, 范厚明, 张晓楠, et al. 求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法[J]. 系统工程理论与实践, 2018.

[9]甘宝, 薛玉玺, 魏文萍. 基于改进遗传算法的车辆路径问题[J]. 交通运输研究, 2015(4):88-94.

[10] Habibeh Nazif, Lai SoonLee. Optimised crossover genetic algorithmfor capacitated vehicle routing problem [J] Applied Mathematical Modelling.Volume 36, Issue 5, May 2012, Pages 2110-2117

[11]W.Y. Szeto, Yongzhong Wu, Sin C. Ho. An artificial bee colony algorithmfor the capacitated vehicle routing problem [J]. European Journal ofOperational Research. Volume 215, Issue 1, 16 November 2011, Pages 126-135

[12]王书勤. 车辆路径问题的蚁群算法研究[D].重庆大学,2008.

[13]陈亮,周晶晶.求解CVRP的改进蚁群系统算法[J].军事交通学院学报,2014,16(05):92-95.

[14]晁晓菲,杨晓龙.带容量约束的车辆路径问题算法综述[J].价值工程,2012,31(05):16-17.

[15]王文蕊,吴耀华.带实际约束的大规模车辆路径问题建模及求解[J].控制与决策,2013,28(12):1799-1804.

[16]袁文涛,孙红.CVRP物流配送路径优化及应用研究[J].软件导刊,2016,15(11):140-143.

[17]向婷. 求解车辆路径问题的智能算法研究[D].西华师范大学,2017.

[18]金焕杰,许峰.基于聚类的混合多目标遗传算法在车辆路径问题中的应用[J].软件导刊,2011,10(06):42-44.

[19]刘敏. 多目标遗传算法在车辆路径优化中的应用研究[D].湘潭大学,2006.

[20]李阳,范厚明.求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法[J].控制与决策,2018,33(07):1190-1198.

[21]仪孝展. 基于改进遗传算法的物流车辆路径规划方法研究与应用[D].西安理工大学,2018.

[22]王刚. 遗传算法在VRP中的应用与研究[D].重庆交通大学,2011.

[23]赵静,孔金生.基于遗传算法和禁忌搜索的混合优化策略[J].计算机工程与设计,2009,30(23):5489-5491.

[24]牟乃夏,徐玉静,李洁,张灵先.遗传禁忌搜索算法收敛性和时间复杂度分析[J].河南理工大学学报(自然科学版),2018,37(04):118-

[25]陈成.基于改进遗传算法的带时间窗的多目标配送路径优化[J].信息技术与信息化,2018(10):48-51.122.

[26]邹书蓉, 黄晓滨, 张洪伟. 有容量约束车辆路径问题的多目标遗传算法[J]. 西南交通大学学报, 2009, 44(5):782-786.

[27] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, ThibautVidal, Anand Subramanian. New benchmark instances for the Capacitated VehicleRouting Problem [J]. European Journal of Operational Research. Volume 257,Issue 3, 16 March 2017, Pages 845-858

[28] Yiyong Xiao, Qiuhong Zhao, Ikou Kaku, Yuchun Xu.Development of a fuel consumption optimization model for the capacitatedvehicle routing problem [J]. Computers amp; Operations Research. Volume 39,Issue 7, July 2012, Pages 1419-1431

[29] Chung-Ho Wang, Jiu-Zhang Lu. A hybrid genetic algorithm thatoptimizes capacitated vehicle routing problems [J] Expert Systems withApplications. Volume 36, Issue 2, Part 2, March 2009, Pages 2921-2936