摘 要

在信息化时代，物流企业开始关注如何减少人力成本，如何提高物流运输效率，做到准时高效的目标。

物流企业可以通过优化车辆调度系统来减少运营成本，现在国内大多数中小型物流企业的解决方案依旧是人工规划，主要依赖人工经验，显然这种规划方式缺少科学理论依据与正确性，同时此种方式也缺少灵活性，难以应对各种突发情况，容错率小。信息时代需要合理运用科学理论解决这个问题，以找到系统中问题的最优解，从而最大限度的降低运营费用。通过本文的科学理论分析，可以减少司机数量，充分利用司机的工作时间，减少车辆无用的行驶里程，从以上几个方面降低运营费用。

为此，本文考虑到现实情况中的各种约束，以最小化系统的运营成本为目标，建立了人车固定的模式对车辆进行调度的数学模型，求解过程中引入了基于贪心策略的超启发式算法并提出了树枚举算法的概念，通过改进树枚举算法使之成为贪心树枚举算法用以生成问题的初始解，将初始解代入禁忌搜索算法用以求解问题的全局最优解。最后使用实例模型求解验证了模型的可行性。

关键词：车辆调度；多车场；禁忌搜索

Abstract

In the information age, logistics companies began to pay attention to how to reduce labor costs, how to improve logistics and transportation efficiency, and achieve the goal of punctuality and efficiency.

Logistics companies can reduce operating costs by optimizing vehicle dispatching systems. Now most domestic small and medium-sized logistics companies still rely on manual planning, mainly relying on artificial experience. Obviously, this kind of planning method lacks scientific theoretical basis and correctness. The method also lacks flexibility, and it is difficult to cope with various emergencies, and the fault tolerance rate is small. The information age requires the rational use of scientific theories to solve this problem in order to find the optimal solution to the problems in the system, thus minimizing operating expenses. Through the scientific and theoretical analysis of this article, you can reduce the number of drivers, make full use of the driver's working hours, reduce the useless mileage of the vehicle, and reduce operating expenses from the above aspects.

To this end, this paper takes into account the various constraints in the real situation, with the goal of minimizing the operating cost of the system, establishes a mathematical model for the vehicle scheduling in the fixed mode of the vehicle, and introduces a super-inspiration based on greedy strategy. The algorithm is proposed and the concept of tree enumeration algorithm is proposed. By improving the tree enumeration algorithm to make it the greedy tree enumeration algorithm to generate the initial solution of the problem, the initial solution is substituted into the tabu search algorithm to solve the global optimal solution of the problem. . Finally, the feasibility of the model is verified by using the example model.

Key Words：vehicle scheduling; multi-vehicle; taboo search

目 录

第1章 绪论 1

1.1 背景 1

1.2 目的与意义 2

1.3 国内外发展现状 2

1.3.1 单车场求解模型与算法研究 2

1.3.2 多车场求解模型与算法研究 3

1.3.3 求解中的不足 5

1.4 论文创新点 5

1.5 论文章节结构 5

1.6 技术方案 6

1.7 本章小节 7

第2章 车辆调度问题分析 8

2.1 问题基本概述 8

2.1.1 问题中的名词解释 8

2.1.2 调度问题的分类 8

2.1.3 本文解决的问题 9

2.2 调度规则 9

2.3 实例数据 10

2.3.1 仓库位置 10

2.3.2 调度时刻表 11

2.6 本章小结 22

第3章 车辆调度问题建模 23

3.1 模型中的变量 23

3.2 模型的目标函数 25

3.3 模型中的约束 25

3.4 本章小结 27

第4章 车辆调度问题优化 28

4.1 解的结构 28

4.1.1 解的字面量 28

4.1.2 解的编码 28

4.2 启发式方法 29

4.3 树枚举算法 30

4.3.1 树枚举算法介绍 30

4.3.2 树枚举算法原理 30

4.3.3 评价函数 31

4.4 禁忌搜索算法 32

4.4.1 禁忌搜索原理 32

4.4.2 禁忌搜索的关键技术 33

4.5 车辆调度问题求解 35

4.5.1 第一阶段求解 35

4.5.2 第二阶段求解 39

4.6 本章小结 41

第5章 实验结果及其优化方法分析 42

5.1实例问题描述 42

5.2结果分析 42

5.2.1 基于贪心策略的超启发式算法生成初始解 43

5.2.2 贪心树枚举算法生成初始解 55

5.2.3 比较两组解的不同 68

5.2.4 禁忌搜索算法生成最优解 68

5.2.5 模型参数对解产生的影响 81

5.2.6 禁忌搜索算法的改进 82

5.3 本章小结 82

第6章 总结与展望 84

6.1 全文总结 84

6.1.1 本文主要结论 84

6.1.2 经济性与环保性分析 84

6.2 研究展望 85

参考文献 86

附录A 88

附录B 99

附录C 110

致谢 123

第1章 绪论

1.1 背景

随着中国特色社会主义经济的蓬勃发展，国家开始鼓励全民创业，鼓励中小型企业发展。自从十二五开始，国家开始更加关注物流行业，出台了一系列的政策，帮扶国内中小型物流企业的改革，将原始的人力高度集中化的物流行业带入信息化的时代。物流企业开始关注如何减少人力成本，如何提高物流运输效率等问题，做到准时高效的目标。

随着城市的不断发展，人们的生活水平不断得到提高，城市内的便利店也越来越多，例如罗森、Today、芙蓉兴盛等中小型连锁便利店。迄今为止，武汉市内的罗森、Today便利店已经超过200家。便利店最主要的目的就是为大众带来便利，因此便利店内销售的商品无需像超市那样大而全，但是必须做到小而精，需要销售畅销的、需求量高的商品，只有这样才能为大众带来便利的同时，又不会去提高自己的运营成本。

便利店内销售的商品必须及时补货，否则会因货物短缺而让便利店损失客户，在客户前失去品牌形象，从而无法树立较好的口碑。但是因为便利店数量之多，零星的遍布在城市的各个角落，因此如果采用从城市仓库直拨运输货物至各个便利店的方式，同时又由于各个便利店地理位置不同，货物需求量不同，补货时间不同，货物配送时间不同，导致这些小批量远距离的配送势必会产生很多资源的浪费，如需要增加更多的司机来完成配送，汽车行驶距离也将变长，车辆的维护费用，以及燃油费用等的增加。这些费用都会体现在最终的商品的售价中，便利店尽管并不像超市那样是价格敏感型商店，但是与其他的便利店相比售价如果过高，同样会失去一部分的客户。因此，便利店需要降低如上所说的中间成本，这样不仅可以降低商品售价，吸引更多客户，提高便利店的口碑，还可以提高企业营业利润。

为了解决如上所说的问题，现在提出一种新的货物配送模式：分级仓库配送策略。商品由一级仓库发往二级仓库，再由二级仓库发往各个便利店。一级仓库负责各个区域二级仓库的货物配给，二级仓库负责城市内一个区或者一个区内部分区域的便利店货物配给。由各个便利店的信息系统反馈给相应二级仓库关于其便利店的货物库存信息，然后二级仓库根据历史数据预测何种货物需要补货、货物的补货量、补货时间点。二级仓库整合各个下级便利店的补货信息，然后再反馈给对应一级仓库关于其的需求信息，一级仓库根据其需求信息安排配送策略，同时根据本地库存量发给各个供应商货物的需求信息。

在此种配送策略下，各个阶段的配送都是大批量短距离的配送。一级仓库发往二级仓库的货物量将比之前采用仓库直拨配送方式的配送量大，而且配送距离也大大缩短。二级仓库发往各个便利店的货物也可以整合几个便利店的货物在一个时间段内进行配送，因此，第二阶段的配送也做到了大批量短距离运输。因此可以更高效的利用车辆，减少车辆与司机的数量及其空驶时间，减少运营成本。

实现上述配送策略的过程中，需要解决几个问题：

第一个问题是确定各个仓库的位置，是根据各个便利店的商品销售量、地理位置等信息确定城市内的二级仓库位置，然后根据二级仓库的货物需求量、地理位置等信息确定城市内的一级仓库的位置。

第二个问题是确定仓库之间的、仓库与便利店之间的配送路线，根据实际车辆行驶路线以及需求量等信息确定配送时间，然后根据配送量以及配送时间等信息确定车辆的调度，最后根据车辆的调度和班次要求等信息确定司机的调度。

1.2 目的与意义

通过以上的背景介绍。此配送策略的规划与实现十分的复杂，每一个问题都值得仔细去探索研究。本论文从其中一个问题切入进行分析研究：一级仓库至二级仓库货物配送的车辆和司机的调度问题。因为一级仓库至二级仓库的配送量较大，所以一般可以简化成直拨配送，即一级仓库发往二级仓库的货物一般只采用一辆车点对点的运输，而不是将几个二级仓库整合起来统一配送。

本文目的在于讨论在以上情况下，并且在国家劳动法律规定以及企业制度允许的条件下，例如：司机最长工作时间，连续驾驶最大时间，不同班次的规则等约束下，如何进行车辆与司机的调度，使用最少数量的司机和最小空驶时间来完成每天指定的运输任务，从这个方面降低运输成本，提高企业盈利率。

对于车辆和司机调度的问题，现在国内大多数中小型物流企业的解决方案依旧是人工规划，主要依赖人工经验，显然这种规划方式缺少科学理论依据与正确性，不能使运营成本可观的得到降低，同时此种方式也缺少灵活性，难以应对各种突发情况，容错率比较小。现在是信息时代，企业需要合理运用科学理论来解决这个问题，这样才能找到问题的最优解，从而最大限度的降低运营费用。通过本文的科学理论分析，通过减少司机的数量，充分利用司机的工作时间，减少车辆无用的行驶里程等方面降低运营费用。

1.3 国内外发展现状

1.3.1 单车场求解模型与算法研究

最简单的车辆司机调度问题(Vehicle Scheduling Problem, VSP)是单车场调度问题（Single Department Vehicle Scheduling Problem, SDVSP）。所有的车辆全部由同一个车场出发，然后执行一系列任务之后返回这个车场。车辆调度表由一系列的任务段与对应执行的车辆组成。为了解决SDVSP，有许多人提出了解决方案，例如分配模型，运输模型和网络流模型^[1][2]。此外，SDVSP可以通过拍卖算法被有效地解决^[3]。虽然SDVSP理论上可以很容易地解决，但放在现实环境中可能会变成一个非常难以解决的问题。例如，Baita 等人提出了一些解决VSP的方法，他们考虑到了以下约束：车辆有可能在完成一个任务之后需要加油;司机可能在完成一个任务之后等待一段时间之后再去执行下一个任务^[4]。此外，他还提出尽量减少司机的数量，最大限度地减少司机的等待时间和司机空驶里程等约束。他还为运输企业提供了一套解决方案，并比较了三种解决方案：（i）考虑加权目标函数的求解器用来求解的数学模型;（ii）考虑不同标准的字典排序的逻辑编程算法;（iii）用多目标遗传算法找到帕累托最优解。在实现确定性优化方法中，根据需求将每天的调度计划适当划分为较小的计划是一个很重要的方法。周聪等人提出了一个基于聚类的生成具有低可变性计划时间的短计划周期方法^[5]。通过聚类方法所产生的每天的部分计划解决了SDVSP。他在上海的交通网络实施了他研究的方法。数值结果表明，适当划分每天的计划可以更准确地降低车辆的使用成本。

1.3.2 多车场求解模型与算法研究

VSP的另一个变体是多车场车辆调度问题（Multi-Department Vehicle Scheduling Problem, MDVSP），其中车辆可以从不同的车场出发执行任务。这种假设导致求解模型变得十分的复杂，例如多元化商品网络流问题。这种MDVSP是十分难处理的，因为它是NP-hard问题^[6]。不过幸运的是已经有研究提出了解决大型MDVSP问题的方法。例如，Löbel解决了在车辆数目、车场规模、车场车辆类型等限制下，最小化车辆运营费用的MDVSP问题^[7]。基于拉格朗日松弛的多元化商品网络流模型开发了一种列生成方法（Column Generation, CG）。他的解决方案方法已经在德国的大型公交网络中得到了测试。测试结果表明拉格朗日松弛是解决大型实际问题的一个关键方法，并且CG与启发式的结合让我们能在少量的迭代与花费较少计算时间的前提下得到带约束LP（Linear Problem）问题的高质量解。Kliewer等人开发了一种时空算法，可显著减少使用在商业环境下的大型运输网络的成本^[8]。Hadjar等人开发了一个与CG，变量修复和分支切割（Branch Cut, B＆C）相结合的分支定界（Branch Bound, B＆B）方法。通过这个方法，作者成功的解决了一个随机生成的问题，问题中最多有6个车场和750个任务。

也有其他研究者提出了启发式方法，例如调度优先/聚类第二的方法，基于最短路径的启发式方法和ILS（Iterated Local Search）算法^[9][10]。Pepin等人比较了这几个B＆C，CG，拉格朗日启发式，禁忌搜索和大型邻域搜索算法（Large Neighborhood Search, LNS）。对随机生成的问题进行计算，计算结果显示列生成算法在给予它充足的计算时间时性能最好，在寻求高质量解时，大型邻域搜索算法是最佳的选择^[11]。当考虑到不同的车辆类型时这个问题会变得更加的棘手，通常的解决方法是启发式方法^[12]。MDVSP也需要考虑车辆调度表中路线所需时间的限制。例如，Haghani和 Banihashemi限制了车辆调度表中任务段的时长，用来表示车辆的燃料消耗。因此，每个公共汽车可以在重新添加燃料之前运行最多t个连续的时间单位。作者改进了夸西分配算法，允许公共汽车返回车场，以便可以加油继续去完成任务。并提出了求解精确解的方法和启发式方法，这两个方法基于以下两个方法:（i）迭代经典的MDVSP夸西赋值模型，每次迭代时消除不满足运行时间约束的不可行解，（ii）通过合并任务段和移除被选中的概率很小的变量来减少搜索空间^[13]。Wang和Shen展示了另一个例子，其中每辆车都在加油之后有运行时间的约束。因此，在执行几次任务后达到最小的燃油储备值之后，车辆必须重新加油。优化问题旨在最小化由两个级别组成的分层目标函数:（i）车辆数量;（ii）总车辆空驶时间。为了解决这个问题，作者开发了一个ACO（Ant Clony Optimization）算法并用几个实例测试了算法的可行性^[14]。

Hassold和Ceder提出了一种用于MDVSP最小化基于车辆数量和空座位的成本的多层网络流量算法^[15]。一组帕累托最优调度表，包括对于每一个任务的推荐车型，将其作为输入。考虑到这些潜在的调度表，问题目标是建立一个最小化的运营成本的调度表。作者分析了不同操作方法的灵活性，例如：（i）允许替换车辆，即任务可以由不同的车辆类型（具有足够的容量）执行，而不是使用调度表中最初分配的车辆来执行;（ii）使用小调度表来建立一个独一无二的调度表。作者在新西兰的奥克兰运输网的两条双向线上测试他们的模型与并与传统的MDVSP算法相比，其工作成本降低了15％。此外，他们还分析了解决方案对服务水平的影响，例如：对等待时间和空座位的影响。

魏金丽等人通过集合覆盖理论对公交线路的调度优化，考虑了多个连续的驾驶段之间的休息时间约束 ^[16]。侯彦娥等人通过混合元启发式算法解决了在人车绑定模式下的车辆调度问题，并用集合覆盖理论改进了前者求出的最优解^[17]。陈明明等人考虑了综合最长工作时间，时间窗口等约束条件，建立了数学模型，并使用用禁忌搜索算法，在调整合适的禁忌表长度之后求解出了最优解^[18]。