摘 要

随着贸易的全球化和电子商务的繁荣，物流产业的发展已经成为一个重要的指标来衡量一个国家的综合国力和国际竞争力。同时社会生产和消费的飞速发展使得物流业对国民经济发展的影响日益突出，在这种环境下，物流模式也发生了巨大的改变，物流服务的客户不再只有单一的需求或供应，现在的客户往往既有供货需求又同时具有集货需求，所以集配一体化的物流运作模式就顺应了这种变化诞生了。集货和配送是物流过程中的两个重要环节，它们在整个物流系统中占有重要的地位。本文研究的就是配送车辆仅服务顾客一次，就能同时满足每个顾客集货和配货需求的集配货一体化的车辆路径规划问题。

本文对集配一体化的车辆路径规划问题的研究背景及研究现状进行了剖析，从而了解了该问题的重要性，并结合实际情况，在综合了配送车辆的可变成本和固定成本的基础上，构建了总成本最小的集配一体化的车辆路径优化模型。本文在对模型的求解方法选择中分析对比了常用的五种启发式算法，选用并改进了遗传算法，通过MATLAB进行编程求得模型的满意解，并通过与同数据的集配货分开情况下的车辆路径规划问题的解进行对比，证明在集配一体化的情况下优化车辆路径能较好地减少配送成本。

关键词：集配一体化；物流配送；车辆路径规划；遗传算法

Abstract

With the globalization of trade and the prosperity of e-commerce, the development of logistics industry has become an important index to measure the comprehensive national strength and international competitiveness of a country. At the same time the rapid development of social production and consumption has influence on the development of the logistics industry to the national economy increasingly prominent, and in this environment, also great changes have taken place in logistics mode, logistics service customers no longer only a single demand or supply, now customers tend to both the supply and demand have set goods demand at the same time, so the set with the integration of the logistics operation mode is complied with this kind of change was born. Collection and distribution are two important parts of logistics process, and they play an important role in the whole logistics system. In this paper, it is studied that the distribution vehicles only serve customers once, and can meet the integration of each customer's collection and distribution requirements in the integrated vehicle path planning.

In this paper, the set with the integration of the vehicle path planning problem of the research background and analyzes the research status quo, to understand the importance of the problem, and combining the actual situation, the comprehensive variable cost and fixed cost of distribution vehicle, on the basis of building the set to minimize the cost of the vehicle routing optimization model of integration. Based on comparing the methods of solving the model selection of the commonly used five kinds of heuristic algorithm, and genetic algorithm are improved, through the MATLAB programming get the satisfied solution in the model, and with the same data set distribution cases separately, comparing the vehicle path planning problem of the solution in the set with the integration of optimization under the condition of vehicle routing can reduce distribution costs.

Keywords: pick-up and delivery; logistics distribution; vehicle routing problem; genetic algorithm

目录

第1章 绪论 1

1.1研究背景及意义 1

1.2国内外研究现状 2

1.2.1 VRP问题的研究现状 2

1.2.2 VRP问题的建模及求解现状 3

1.3研究内容及思路 4

1.3.1研究内容 4

1.3.2研究重难点 4

1.3.3论文结构 5

1.4 本章小结 6

第2章 集配一体化的车辆路径规划模型的构建 7

2.1理论概述 7

2.1.1集配一体化VRP问题的基本概念 7

2.1.2模型的影响因素 8

2.1.3模型优化目标选择 9

2.2问题描述与模型 9

2.2.1问题描述 9

2.2.2模型假设 10

2.2.3符号说明 10

2.2.4模型构建 10

2.3 本章小结 11

第3章 算法的选择与应用 12

3.1算法的选择 12

3.2算法的应用与改进 14

3.2.1传统的遗传算法介绍 14

3.2.2遗传算法的改进 15

3.3 本章小结 20

第4章 案例分析 21

4.1 案例描述 21

4.2 参数设置 22

4.2.1模型参数设置 22

4.2.2算法参数设置 22

4.3 结果分析 23

4.3.1集配一体化的VRP问题结果分析 23

4.3.2两种物流模式结果对比 25

4.4 本章小结 27

第5章 总结与展望 28

5.1 全文总结 28

5.2 研究展望 29

参考文献 30

附录 32

致谢 40

第1章 绪论

1.1研究背景及意义

当今世界，物流已经被越来越多的人认为是企业在减少物资消耗、提高劳动生产率之外创造利润的重要来源，所以想要提高企业的经济效益，获得更多的利润，改进物流作业流程已经成为了一个重要的途径。物流水平的高低已经对企业竞争力的大小造成了很大的影响，不仅如此，一个地区的物流业的发展水平也影响着这个地区的经济发展。今天，物流业的发展呈现稳稳的上升趋势，欧洲和美国等经济发达国家都开始牢牢抓住物流这棵摇钱树，物流的发展已经趋向于成熟，而我国物流业起步较晚，现在还处于逐渐完善的阶段。

集货和配送作为物流的两个重要环节，其要求就是在满足目标顾客需求的前提下完成一系列诸如装卸、拣选等作业的活动，基本目标是要在及时有效地满足顾客需求的前提下控制成本。在物流集货和配送业务中，车辆的调度问题对物流企业降低成本、提高顾客满意度、增加经济效益的影响较大，同时也需要考虑很多影响和限制因素，尽量以最小的成本满足顾客的所有要求。

现阶段，传统的物流管理主要集中在材料的正向流动上。然而，新环境法规的颁布和对产品再利用的激励措施增加了近年来供应链的逆向流动。对材料或产品的逆向流动的管理在物流管理中开辟出了一个新的领域——逆向物流。逆向物流通过重新获得在物流过程中未充分利用的价值来产生额外的收益，但逆向物流也存在它自己的问题：路径规划和车辆调度者需要考虑从一个客户的单个车辆运送和取货。单一的集货或配送业务，车辆只对客户进行单纯的集货或配送业务，这种模式下的启程和回程车辆的车辆空间使用率较低，会造成时间和成本上不必要的浪费。针对这种不必要的资源浪费情况，本文提出了改进的措施，就是允许车辆在同时存在集货与配货需求的顾客点处同时进行集货与配货作业。这种同时集货和配货的物流模式被称为集配货一体化的车辆路径规划问题（VRPSPD）。VRPSPD是一个NP-hard问题，因为当我们将所有的接收需求或所有的交付需求都设置为零时，问题就会降低到一个已知的NP-hard问题的容量化车辆路径问题。VRPSPD与反向运输的车辆路径问题密切相关，该问题要求在从回程顾客处取货之前，必须向线上的顾客交付所有的货物。虽然该问题的求解较为复杂，但它对提高物流企业的经济效益，减少成本有着重要的意义。

本文对有关条件进行了符合模型假设的筛选，选取总费用最少为建立模型的优化条件，构建集配一体化的车辆路径规划模型，采用合适的算法求解模型，并与单独集货作业的成本加上单独配货作业的成本进行对比，用以凸显集配货一体化的VRP成本最少的优势，进行集配一体化的车辆路径优化更能提高物流过程的效益。

1.2国内外研究现状

1.2.1 VRP问题的研究现状

早在1959年，Dantzig和Ramser首次定义了车辆路径问题（VRP）^[1]。它是指由物流中心向一定数量的顾客提供配送服务，每个顾客有不同数量的货物要求，在一定条件的约束下（如，时间约束、载重量约束等），物流中心安排车辆服务顾客，并在满足顾客需求的前提下，达到物流中心的业务目标（如，总配送成本最少、总配送时间最短、运输路程最短等）的车辆路径规划，一般的车辆路径问题如图1.1。

图1.1 一般车辆路径问题

近几年来，随着物流社会地位的不断提升，VRP问题的研究也越来越成熟，但如何使理论更能够贴近现实中的配送问题，解决实际的配送需求逐渐成为了越来越多研究者关注的问题。

针对保质期较短货物的VRP问题，钟定业、李鹏飞、樊世清等人对这种有时间窗约束的冷链物流配送问题有了一定的研究成果。钟定业等人针对海南花卉冷链物流配送问题进行了研究^[2]，他运用扫描算法对原配送路线进行了时间和成本等方面的优化，为降低花卉企业运输成本和保障花卉在运输过程中维持新鲜提供了理论支持；李鹏飞等人建立针对水产品运输车辆配送路径的优化模型^[3]，他们针对水产品易变质、不易保存的特点，在数学模型中加入了水产品保鲜时间窗和路况条件的不确定性约束，有助于水产的保鲜运输；樊世清等人对易变质产品的运输也提出了自己的解决方案^[4]，他们针对生鲜产品易变质、不易保存等特性，综合考虑了运输过程中的各成本和生鲜产品的时间窗问题，建立了农产品冷链物流车辆配送路径优化模型，有效地减少了配送的总成本。

朱婷等人针对危险化学品道路运输路径优化问题，考虑了运输时间与运输风险及道路节点的服务时间窗限制，用蚁群算法进行了有效地求解^[5]。通过该研究，运输企业可依据不同时刻的运输结果制定每班车辆的出发时刻表，危险化学品的监管部门可合理调节各路径运输时间及风险来规避危险化学品泄漏的危险情况。

梁展等针对战时军用物资消耗量大、后勤保障任务艰巨的情况，探索了战时军用物资的运输调度VRP问题，建立了多起点多收点的物流配送模型并运用Dijkstra算法确定了最优运输路线^[6]。这一研究有效地保证了军用物资的运达，提高了后勤保障能力，为我国的军事领域做出了贡献。

王博弘等对成品油二次配送的国内外研究成果进行了调研^[7]，通过此次调研发现：主动配送随着智能物流的发展将成为成品油二次配送未来的发展趋势。

除了对VRP问题在农产品运输、危险品运输和军事调度等方面的研究，随着绿色物流概念的提出，学者们开始将研究的焦点集中在物流配送过程中的能耗问题和碳排放问题上。杨萍等人探索了基于低能耗、低碳的车辆路径规划问题，建立了计算运输过程中油耗的模型^[8]，这一研究为有效减少物流过程中的能耗和碳排放提供了理论支持。王思静在传统车辆路径问题的研究基础上，考虑了冷链运输企业实际配送中会遇见的问题并将碳排放纳入成本考虑，构建了一个符合农产品冷链物流实际的车辆路径问题模型^[9]，在规划车辆路径的过程中，她将环境保护考虑在内，为减少物流过程中的碳排放提供了理论依据。针对低碳的城市共享单车调度杂乱无章的问题，刘兆仁等人在对公共自行车调度问题进行分析的基础上，利用遗传算法有效求解自行车调度问题^[10]。

1.2.2 VRP问题的建模及求解现状

车辆路径规划问题是一个NP-hard问题，在VRP问题研究的初始阶段研究者主要将研究聚焦在正向物流上，但随着逆向物流的发展越来越成熟，他们把逐渐正向物流的配送和逆向物流的回收融合到一起形成了VRPSPD问题，而VRPSPD问题的求解就更加复杂了。针对这一阶段的研究，Golden等人最早提出可以在车辆配送过程中先集货后配货，允许车辆在配送过程中先访问有集货需求的客户^[11]；Min首次求解顾客既有集货需求又有配送需求的车辆路径规划问题，他首先把顾客进行了分组，然后再求解每组顾客的旅行商问题^[12]；Halse针对当顾客既需求集货又需求配货的情况，用先分组方法把客户分配给车辆然后再规划路线，然后使用3-opt方法优化路径^[13]；Gendreau等人开了将禁忌搜索思想应用到车辆路径优化领域的先河，求解了同时存在集货和配货需求的旅行商问题^[14]；Jim Ai等人用粒子群算法求解了既有集货需求又有配货需求的车辆路径规划问题^[15]；Dridi等人采用改进遗传算法，以运输距离和物流总成本最小化为优化目标，求解了时间窗约束下的集配一体化车辆路径问题^[16]；Cordeau等人采用精确算法中的分支定界法，遵循先进先出原则，求解了集配一体化的车辆路径规划问题，并用该方法求解了有50个节点的实例，验证了该算法的可行性和有效性^[17]。

虽然我国对于这方面的研究起步较晚，但随着物流产业的飞速发展，越来越多的学者也取得了针对VRP问题的研究成果。郭耀煌等人针对有时间窗约束的非满载情况下的VRPSPD进行了研究^[18]；郎茂祥用模拟退火算法求解了集配一体化的车辆路径规划问题，又采用禁忌搜索算法对时间窗约束下的集配一体化车辆路径规划问题进行了求解，并用含有20个客户点的实例验证了算法的可行性^[19]；孙小年等人采用4位数的遗传编码改进了遗传算法，有效地提高了解的质量^[20]；刘晓勇等人改进蚁群算法，能够较快地收敛到较高质量的解，并在启发式信息中加入距离矩阵和路径节约矩阵等信息，求解了受到容量限制的VRP问题^[21]；曹平方等将用于旅行商问题（TSP）的分枝定界法加以改进，设计出了一种克服了用启发式算法求解车辆路线问题结果精确度不高缺点的车辆调度问题的精确算法^[22]。

1.3研究内容及思路

1.3.1研究内容

为了提高现代物流企业的服务水平和服务质量，减少车辆运输成本，提高客户满意度，实现资源的优化配置，从而取得更高的经济效益，本文分析集货和配送一体化车辆调度的影响因素，以运输总成本最低为目标，考虑载重量和容量限制等要素，建立了集配一体化的VRP模型；为了选择合适的算法求解已建立的数学模型，减小求解结果的误差，本文分析常用的五种启发式算法，基于已建立的模型，采用最适合本模型的遗传算法求解，并与先集后配的优化结果进行比较，以此证明同时集货和配货能带来更低的配送费用。

1.3.2研究重难点

（1）构建集配一体化的车辆路径规划数学模型，突出集配一体化的特点，即建立的模型要突出同时进行集货和配送的特点；

（2）改进传统的遗传算法，使其适合求解已建立的集配一体化的车辆路径优化模型；

（3）运用MATLAB编写改进后的遗传算法的程序，并验证程序的可行性。

1.3.3论文结构

（1）掌握本文研究问题的研究背景及意义，了解其研究现状及求解现状，根据研究内容规划论文的组织结构如图1.2；

图1.2 论文组织结构

（2）综合模型的影响因素和目标选择，对模型进行假设，建立总费用最少的集配一体化的车辆路径规划模型；

（3）针对本文的集配一体化的车辆路径规划模型，对传统的遗传算法进行改进，以突出集配一体化的特点并能较高效地寻找全局最优解，运用MATLAB编程求出最优解；

（4）设定参数并进行集配一体化的案例分析，并与单独进行集货作业加上单独进行配货作业的结果进行比较，以证明集配一体化的车辆路径优化能更够节约成本；

（5）对本论文进行结论总结并说明今后的研究展望。

1.4 本章小结

本章分析了VRP及VRPSPD问题的研究背景及意义，掌握了其国内外研究现状，了解了集配一体化的车辆路径规划问题的研究是有实际意义的，总结了本文的研究内容和研究思路，点明了研究的重难点，并根据研究内容规划了论文的组织结构。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：