分时段配送车辆调度问题的禁忌搜索算法

[摘要] 建立了分时段配送车辆调度问题的数学模型，同时采用禁忌搜索算法计算优化的配送线路和配送时间，并采用实例进行仿真计算。计算结果表明算法的计算效率较高，收敛速度较快，计算结果也比较稳定。

[关键词] VSP问题禁忌搜索算法车辆调度

目前，物流配送车辆调度问题的研究主要集中于软时间窗或硬时间窗的配送车辆调度问题，其求解困难，而且企业的配送成本也往往会很高。本文对不同客户的实际配送需求进行分析，提出了分时段配送车辆调度问题，即要求以最少的车辆、最少的费用在客户选择的时间段（时间段可由企业预先确定，并供客户自由选择）内完成配送任务。分时段配送车辆调度问题的解决能够有效促进企业以尽可能低的成本，提供较高水平的客户服务，具有十分重要的现实意义。

禁忌搜索算法是求解最优解的智能化算法，它引入了人工智能技术，仿效人类行为，并应用一些学习规则确定搜索方向，以避免解的局部循环。目前，禁忌搜索算法在车辆调度领域得到了广泛的应用，如Gendreau、Jiefeng、Barbarosoglu、I-Ming Chao、蔡延光、郎茂祥等都曾利用禁忌搜索算法求解配送车辆调度问题，并取得了多项研究成果。本文设计的禁忌搜索算法求解分时段配送车辆调度问题，不仅可以取得良好的计算结果，而且算法的计算效率较高，计算结果也较稳定

一、问题描述

本文提出的分时段配送车辆调度问题是指将配送时间划分成上午和下午两个时段，客户自由选择。与硬时间窗的配送车辆调度问题相比，时间约束比较宽松，求解相对容易，而且能够使企业能够在满足客户配送要求的前提下，以较低的成本完成配送任务。分时段配送车辆调度问题的求解步骤如下：

1.客户根据自身的时间安排选择上午配送或下午配送，上午时段和下午时段的划分可以由企业根据具体情况来设定。

2.对分时段配送车辆调度问题采用禁忌搜索算法进行求解，获取满足客户配送要求的优化的车辆运行线路。

3.计算到达每个配送点的预定时间，再根据道路交通状况计算预定到达的时间窗。然后通知客户在该时间窗内准备接收货物。

二、数学模型

一般地，分时段配送车辆调度问题的具体描述为：有一个配送中心，使用容量为Q吨的车辆给n个配送点P1，P2，P3，…，Pn配送商品。已知配送点i的货运量为gi(i=1，2， …，n)，且gi

1.指定在某一天送货，并要求在上午配送。

2.指定在某一天送货，并要求在下午配送。

求在满足各配送点时间约束的前提下配送费用最小的车辆运行线路，并计算到达每个配送点的配送时间。

一般认为，派出一辆车的固定费用远远高于车辆行驶费用，所以求解目标确定为在极小化车辆的前提下，再极小化运输费用。

为了方便构造数学模型，将配送中心编号为0，配送点i编号为1，2， …，n。定义变量如下：

cij表示从配送点i到配送点j的运输成本，与两点之间的距离成正比。

si表示到达配送点i的时间，由始发时间（ST）、行驶时间(t)、卸货时间(ut)构成。

tij表示从配送点i到配送点j的行驶时间；uti表示在配送点i进行装卸作业的时间。

Pti表示第i个配送点的时间约束，Pti=1表示上午时段,Pti=2表示下午时段。

则可得分时段配送车辆调度问题的数学模型如下：

三、 算法设计

输入：各配送点的配送任务和各配送点间的距离。

输出：优化的车辆调度安排和达到各配送点的预定时间窗。

原理：采用禁忌搜索算法进行求解。

算法的主要步骤如下：

步骤1：选定一个初始解Xpop；令禁忌表tabu list=Φ；

步骤2：若满足终止准则，则转步骤4；否则在一定搜索方向产生移动值Fmove，在Xpop的领域D(Xpop)中选择出满足禁忌要求的侯选解CD（Xpop），转步骤3。

步骤3：在CD（Xpop）中选一个评价最好的解Xbest,令Xpop=Xbest，更新禁忌表tabu list，转步骤2。

步骤4：输出计算结果，停止。

其中，初始解、领域结构、禁忌表、禁忌长度、评价函数的确定是禁忌搜索算法设计的核心，此外还包括终止准则的确定。

1.初始解。任何禁忌搜索算法需要一个初始解以开始其局部搜索过程，本算法将以随机方式产生初始解。但初始解必须满足以下条件：

（1)每条线路上车辆运输能力的限制。

(2)客户选择时间段的要求。

(3)每条线路的上午配送点数量基本保持一致，这主要是为了确保每条线路的上午配送任务比较均衡，而且还可以使每条线路完成上午配送任务的时间比较接近。

2.领域结构。禁忌搜索算法是一种基于领域搜索技术的算法，本文将领域结构确定为同一时间段内任意两个城市的互换(SWAP)操作，每个状态的领域解有C2n1+ C2n2=n1*(n1-1)/2+ n2*(n2-1)/2个，其中n1表示上午配送点的数量，n2表示下午配送点的数量。

3．禁忌表。禁忌表用于记录已经到达过的局部最优点，这样在下一次搜索中，就可以利用禁忌表的信息，不再或有选择的搜索这些点，以此来跳出局部最优点。在搜索过程中，局部最优点会被作为禁忌对象加入禁忌表的最末位置，随着新解的不断加入，老解将从禁忌表的头部删除，从而实现自动解禁。

4.禁忌长度。禁忌长度是指被禁忌对象不允许被选取的迭代步数。当禁忌表中的禁忌对象经过一定步数的移动后，该禁忌对象即被解禁，并可以作为下一步的搜索方向。本文采取定长禁忌长度，其值大小可根据问题的规模来确定。

5.评价函数。采用禁忌搜索算法求解分时段配送车辆调度问题时，首先判断侯选解是否满足约束条件，然后计算侯选解的目标函数值。本文以目标函数作为解的评价方法，在满足约束条件的前提下，其目标函数值越优，则解的质量越高。如果当前最优解不是禁忌对象，则可以作为下一步的搜索方向。

6.终止准则。程序运行超过给定的最大迭代步数时，则算法终止。

四、实验分析

下面以配送点数为12的非满载VSP为例，配送点编号i为1，2，…，12；配送中心的编号i为0；配送点i坐标为(xi ，yi) ，单位为公里。每个配送点的配送货物的量为gi （gi

表 配送点数为12非满载VSP的原始数据

假设每辆车的平均行驶速度为40公里/小时；车辆的吨位 Q = 5 吨；始发时间 ST = 8点；午餐时间 LT = 1个小时（午餐时间安排在上午配送完成之后）。

根据，求出各点之间的距离矩阵，假设cij=cji，cii＝M(M为一趋于无穷大的正数)；再确定运输车辆的数量。

迭代步数取100，计算时间0.3s，程序仿真的结果如下：

1.行使总里程为345公里，通过枚举法可以证实为全局最优解。

2.优化的车辆运行线路为：

线路1：0-10-3-6-7-4-1-0 运输量：4.5吨

线路2：0-12-5-8-9-11-2-0 运输量：5吨

相应的配送时间安排为：

3.计算到达每个配送点的时间窗。假设配送时间误差Φ确定为正负15分钟，则到达每个配送点的时间窗为：

五、结论

本文首先根据不同的客户需求提出了分时段配送车辆优化调度问题，然后建立了数学模型，并作了补充说明。该数学模型具有较高的实用与理论价值，而且表述清晰，直观，易于理解。另外，本文还设计了禁忌搜索算法求解分时段配送车辆优化调度问题，并运用实例进行实验计算。计算结果表明，该算法能够获得较好的计算结果，而且算法的计算效率较高，计算结果也较稳定。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。