摘 要

物流配送是物流系统中非常重要的环节之一，现代物流成本占据物流系统成本的较大比例，减少物流成本成为提高企业竞争力的重要途径，而运输成占据近一半的物流成本，所以节约运输成本能有效提高经济效益。车辆路径问题是主要研究最小化物品运输成本的物流配送问题，近几十年已经取得了丰富的研究成果。

本文对车辆路径问题的历史和研究现状进行了分析和总结，对常用的求解算法的原理、特点及适用范围进行了一定的概括，介绍了一些关于约束规划的理论知识，包括其基本原理及组成部分等，并基于此确定了本文研究方法和研究目标。同时结合生活实际提出了本文研究的问题——带时间窗的车辆路径问题，并建立了以顾客时间窗和顾客货物需求量等为约束条件，以最小化配送总路程为目标函数的VRPTW约束规划模型。

论文思路主要由两部分组成。第一部分是提出多种优化基本模型的方法，例如减少车辆数量、消除车辆对称性、增加冗余约束、更改搜索方式等等。基本模型可以充分描述带有时间窗约束的车辆路径问题，但合理增加一些事实上满足实际情况的冗余约束能够使得求解效果更优。第二部分是将本文提出的基于约束规划的VRPTW模型与基于大规模局部搜索的VRPTW模型相结合，将求解约束规划模型的解作为初始解提供给大规模局部搜索的VRPTW模型继续求解，增加了模型的多样性与算法的交互，力求实现更好的求解效果。最后通过VS2013编程在计算机上实现VRPTW的约束规划模型及大规模局部搜索算法，以Solomon的标准测试包中的系列数据进行模型及算法的测试，对实验结果进行分析比较之后，能够验证了本文模型及算法的有效性。

关键词：车辆路径问题；约束规划模型；大规模局部搜索

Abstract

Distribution is an important part of the system of logistics. Logistics cost occupy a large proportion of the cost of the logistics system. Reducing logistics cost has become an important way to improve the competitiveness of enterprises. Transport accounts for nearly half of logistics costs, so save on shipping costs can increase economic efficiency. Vehicle routing problem is studied to minimize the physical distribution of goods transport costs, and a wealth of research has been made in recent decades.

In this article the history and current research about vehicle routing problem and the scope, characteristics and principles of commonly used algorithms are analyzed and summarized. It introduces some theoretical knowledge on constraint programming, including the basic principles and components. Then the research methods and the objectives of this article are determined. Combined with real life presents this article's problem--the vehicle routing problem with time Windows, and set up constraints about customer time windows and customer demand for the goods. The objective function of the VRPTW constraint programming model is to minimize distribution total distance. This paper consists of two parts. First part puts forward a variety of optimization method for the basic model, such as reducing the number of vehicles, eliminating vehicle symmetry, adding redundant constraint, changing the search mode and so on. Basic model can fully describe the VRPTW problems, but reasonable increasing in some redundant constraints meeting the actual performance makes the solving more effective. Second part proposes a method that gives the constraint programming model’s solutions to another model based on large local search as an initial solution for trying to find a better solution, so that the diversity of models are increased and better solution can be found. Finally, I use VS2013 to model VRPTW with constraint programming and implement the large local search algorithm. The Solomon's standard test kits are used for testing the model and the large local search algorithm, after the comparison of the experimental results, we can verify the validity of the model and the algorithm.

Key Words: Vehicle routing problem; Constraint programming model; Large local search

目录

摘要 I

Abstract II

第一章 绪论 1

1.1 选题背景及研究意义 1

1.2 国内外研究现状 1

1.3 研究的基本内容与目标 3

1.4 拟采用的技术方案及措施 3

1.5 技术路线图 4

第二章 车辆路径问题及约束规划研究 5

2.1 车辆路径问题 5

2.1.1 标准车辆路径问题及其数学模型 5

2.1.2 车辆路径问题的变型 6

2.2 车辆路径问题的算法 6

2.2.1 精确算法 6

2.2.2 启发式算法 7

2.3 约束规划 10

2.3.1基本原理 11

2.3.2 组成部分 11

第三章 带时间窗车辆路径问题的约束规划模型 13

3.1 问题描述 13

3.2 假设条件 13

3.3参数及变量定义 13

3.4 约束规划模型 14

第四章 模型改进及数据测试 17

4.1模型的改进 17

4.1.1减少车辆数量 17

4.1.2确定已知变量取值 17

4.1.3消除车辆对称性 18

4.1.4增加路径变量的冗余约束 18

4.1.5调用IloAllDiff约束 19

4.1.6更改搜索方式 20

4.1.7起始点前身变量的三种约束方式 20

4.1.8更好的值域选择 21

4.1.9约束条件的布置顺序 21

4.1.10求解时间的输出 22

4.2实验分析 22

4.2.1数据测试 22

4.2.2 结果分析 23

4.3 大规模局部搜索算法设计及验证 24

4.3.1 大规模局部搜索算法设计 24

4.3.2算法验证结果 25

第五章 总结与展望 26

5.1 总结 26

5.2 展望 26

5.3 社会经济效益分析 26

致谢 28

参考文献 29

附录 31

第一章 绪论

1.1 选题背景及研究意义

物流是指物品从其供应地向其接收地的实体流动的过程，随着现在全球经济一体化趋势、市场竞争的日益加剧、科学技术的不断进步和消费者需求水平的个性化和多元化，物流业的发展水平很能体现一个国家的经济发展水平和综合国力的强弱。物流业作为国民经济发展支撑的重要产业之一，日益受到企业的关注，被称作“第三利润源泉”。据测算，现代物流成本大约占据企业成本的30%~50%，所以发展物流业是大幅降低企业运作成本、有效提高企业市场竞争力的重要途径。

目前，我国的物流业与其他的发达国家相比，在成本控制及运输效率等等方面还做得不够好，有很大的提升空间，尚处于一个初级阶段。在物流成本占比方面，我国的物流成本占国家GDP的比率要比美、英、日等发达国家高出很多，所以我们国家的物流效率及成本控制还有很大的提升空间，如何降低物流成本是目前物流业中亟待解决的关键问题之一。在物流成本构成方面，运输成本接近总成本的一半，远超过保管费用和管理费用，而配送路线优化又能有效降低运输成本，并能大大减少能源浪费和空气污染，因此研究优化物流运输路线的方法就很具有实际意义。