1.1背景

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

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

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

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

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

1.2目的与意义

通过以上背景的介绍，便利店物流配送方式有了新的方式，此配送方式需要解决几个问题。

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

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

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

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

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

1.3国内外发展现状

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

VSP的另一个变体是多车场车辆调度问题（MDVSP），其中车辆可以从不同的车场离开去执行任务。这种假设导致求解公式变得十分的复杂，例如多元化商品网络流问题。这种MDVSP是十分难处理的，因为它是NP-hard问题^[6]。不过幸运的是已经有研究提出了解决大型MDVSP问题的方法。例如，L#246;bel解决了在车辆数目、车场规模、车场车辆类型等限制下，最小化车辆运营费用的MDVSP问题^[7]。作者基于拉格朗日松弛的多元化商品网络流公式开发了一种列生成方法（CG）。他的解决方案方法已经在大型德国公交网络中得到了测试。测试结果表明拉格朗日松弛是解决大型实际问题的一个关键方法，并且CG与启发式的结合让我们能在通过少量的迭代与花费较少计算时间的前提下得到带约束LP问题的高质量解。Kliewer等人开发了一种时空算法，可显著减少使用在商业环境下大型运输网络的大小^[8]。Hadjar等人开发了一个与CG，变量修复和分支切割（B＆C）相结合的分支定界（B＆B）方法。通过实现这个解决方法，作者成功的解决了一个随机生成的问题，问题中最多有6个车场和750个任务。也有其他研究者提出了启发式方法，例如调度优先/聚类第二的方法，基于最短路径的启发式方法和ILS算法^[9][10]。Pepin等人比较了这几个B＆C，CG，拉格朗日启发式，禁忌搜索和大型邻域搜索算法（LNS）。对随机生成的问题进行计算，计算结果显示列生成算法在给予它充足的计算时间时性能最好，在寻求高质量解时，大型邻域搜索算法是最佳的选择^[11]。当考虑到不同的车辆类型时这个问题会变得更加的棘手，通常的解决方法是启发式方法^[12]。MDVSP也需要考虑车辆调度表中路线所需时间的限制。例如，Haghani和Banihashemi限制了车辆调度表中任务段的时长，用来表示车辆的燃料消耗。因此，每个公共汽车可以在重新添加燃料之前运行最多t个连续的时间单位。作者增强了夸西分配算法，允许公共汽车返回车场，以便可以加油继续去完成任务。提出了精确的方法和启发式的方法，这两个方法基于以下两个方法:（i）迭代经典的MDVSP夸西赋值公式，每次迭代时消除不满足运行时间约束的不可行解，（ii）通过合并任务段和移除被选中的概率很小的变量来减少搜索空间^[13]。Wang和Shen展示了另一个例子，其中每辆车都在加油之后有运行时间的约束。因此，在执行几次任务达到最小的燃油储备之后，车辆必须重新加油。优化问题旨在最小化由两个级别组成的分层目标函数:（i）车辆数量;（ii）总车辆空驶时间。为了解决这个问题，作者开发了一个ACO算法并车时在了几个例子上^[14]。Hassold和Ceder提出了一种用于MDVSP最小化基于车辆数量和空座位的成本的多层网络流量算法^[15]。一组帕累托最优调度表，包括对于每一个任务的推荐车型，将其作为输入。考虑到这些潜在的调度表，问题目标是建立一个最小化的运营成本的调度表。作者分析了不同操作方法的灵活性，例如：（i）允许替换车辆，即任务可以由不同的车辆类型（具有足够的容量）执行，而不是在调度表中最初分配的车辆来执行;（ii）使用小调度表来建立一个独一无二的调度表。作者在新西兰的奥克兰运输网的两条双向线上测试他们的模型与并与传统的MDVSP算法相比，其工作成本降低了15％。此外，他们还分析了解决方案对服务水平的影响，例如：等待时间和空座位。王森磊基于树生成算法生成初始解，树生成算法生成效率高，充分利用了生成树的特性^[16]。陈明明考虑了多班制度下的MDVSP问题^[17]。刘涛考虑了在一个长时间段内驾驶员的排班问题，例如一个月内如何排班可以使每一个驾驶员的工作时间基本一致，而且还满足国家规定的休假规则^[18]。Leone 等人利用GRASP算法解决了此问题，并将此方法与精确解求解方法做了比较，由计算结果表明，该算法可以用于大型问题，精确解求解方法甚至会在大型问题中无法求得最优解^[19]。Christors 等人开发了一种算法CGQS，当车辆完成任务之后无需返回车场，而是停留在特定地点，以便于更快的开始第二天的任务，该算法用于研究如何调度车辆，使之在完成当日任务的情况下又能更快的开始第二天的任务，从而降低运营成本^[20]。Dung-Ying Lin等人则开发了一个列生成算法，他们将此问题分解成了两个问题，一个主问题与一个子问题，主问题优化覆盖的规则的数量，而子问题则改进主问题求出的遵循的指定规则的解^[21]。Piotr Lechowicz等人也利用GRASP实现了对航空运输网络的优化^[22]。此外Michalis等人创新性的使用了蚁群算法动态规划了车辆调度问题^[23]。

2.1基本内容

(1)根据现实抽象出问题实例：

本论文从一级仓库至二级仓库的货物配送、以及一级仓库之间、二级仓库之间的货物调运作为切入点，来求解此情况下的司机车辆调度问题。本论文将在武汉市内模拟多个一级仓库与二级仓库的地理位置，并在遵从国家劳动法律规定下进行车辆司机调度，例如最长劳动时间，最长连续驾驶时间，班型时间规则等，尽量减少司机与车辆的使用数目及其空驶时间，从而降低运营成本。

(2)根据问题实例进行数学建模：

根据仓库每天需要的发货次数以及发货时间、每个仓库已存在司机的数目、公平性原则等约束建立数学模型，引入空驶成本，司机等待时间的隐形成本来构建目标函数。求解目标函数的最小值，来求解此问题的最优调度方案。

(3)利用智能算法求解模型：

首先利用启发式方法生成初始解，采用哪个仓库的司机能更快速执行此班次则优先选用此司机的策略来生成初始解，然后再用禁忌搜索算法来求解最优解。在求解过程中对邻域进行交换、插入生成新的邻域，采用禁忌表防止陷入搜索循环，当迭代指定次数之后终止求解过程。

2. 2 设计技术方案

(1)使用启发式方法和树枚举算法，生成可行的初始解。

(2)使用禁忌搜索算法，调整禁忌表的长度，寻找合适的邻域搜索方案。

(3)模拟合理的仓库地理位置，生成合适的运输时间表，建立数学模型。

(4)对数学模型进行求解，并对生成结果进行分析。

(5)对求解方案进行分析，探讨此求解方案的优势与不足。