多车场车辆优化调度模型及算法

李臻; 雷定猷

多车场车辆优化调度模型及算法

李臻,
雷定猷

中南大学交通运输工程学院, 湖南长沙 410075

详细信息

作者简介:
李臻(1980-),男,河南荥阳人,中南大学硕士研究生,从事运输规划与管理研究.

中图分类号: U491
计量
- 文章访问数: 473
- HTML全文浏览量: 148
- PDF下载量: 519
- 被引次数: 0
出版历程
- 收稿日期: 2003-05-17
- 刊出日期: 2004-02-25

Model and algorithm of multiple depot transit vehicle scheduling

School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China

More Information

Author Bio:
LI Zhen(1980-), male, graduate student, 86-731-5641047, lzh_csu@163.com

Article Text (Baidu Translation)

摘要

摘要: 针对多车场满载运输问题的特征, 提出了多车场车辆优化调度的数学模型, 设计了求解该问题的启发式算法, 应用结果表明, 该算法是可行的。
- 车辆调度 /
- 多车场 /
- 启发式算法 /
- 满载
Abstract: Based on analyzing the characteristic of the multiple depot vehicle scheduling (MDVS) problem with full loads, this paper put forward a optimization model, designed heuristic algorithm. Application example shows that this algorithm is feasible.
- vehicle dispatch /
- multiple depot /
- heuristic algorithm /
- full loads

HTML全文

0. 引言

车辆调度是各专业运输公司和大型企业部门的一项日常性工作。其目的是在一系列已知的装货点和卸货点组成的运输网络中, 选择适当的行车路线, 将运输任务合理分配, 在满足一定的约束条件 (如车辆容量、容积限制、行驶里程限制等) 下, 达到一定的目标 (如总路程最短、费用最少、使用车辆最少等) 。

由于车辆优化调度问题属于NP难题, 只有在任务数和车辆数较少的时候, 才能求得精确解, 因此, 启发式算法就成为人们研究该问题的自然选择。如Clarke和Wright提出的节约法^[1], Gillett和Miller提出的扫描法^[2], Fisher和Jaikumar建立的一般分派算法^[3~5]等。这些算法为求解车辆路径问题提供了有效的方法, 但是多为针对单车场问题或非满载问题的, 对于多车场满载情况下车辆调度的问题却讨论甚少^[6,7]。文献[6]将此问题等价为一个广义指派问题, 然后用SA算法将其分解为单车场问题, 最后用修正的Clarke-Wright启发式算法给出单车场问题的所有巡回路线;文献[7]从一般运输问题的解出发将其连通来构造行车路线。本文针对此问题的特点构造了启发式算法。

1. 多车场车辆调度数学模型

1.1 问题描述及运输网络模型

设某运输公司一个工作日要完成的工作任务共有n项, 其运输量分别为g₁, g₂, …, g_n, 可将按吨位计算的运输量换算为完成该项任务所需的整车次数 (a₁, a₂, …, a_n) 。另设公司共有M个车场用来停放空车 (每天发出空车和停放空车) , 车场和各项货运业务均处于同一连通的道路网上, 见图1。

图 1 MDVS运输网络

Figure 1. MDVS transportation network

下载: 全尺寸图片幻灯片

将每一项业务用一个虚拟点——“重载点”表示^[6], 记为i, 见图2。汽车由重载点i到重载点j为空车行驶, 空驶距离d_ij等于从第i个重载点的卸货点到第j个重载点的装货点之间的距离, 一般

图 2 重载点及其之间的距离

Figure 2. Full loads sites and distance from each other

下载: 全尺寸图片幻灯片

$d_{j i} \neq d_{i j}$

一辆车从某个车场出发, 驶向第一项任务的装货点, 在完成第一项任务后又驶向另一项任务的装货点, 从而形成了一条一段空车行驶, 一段重载行驶, 并且在完成最后一项任务后, 就近返回某个车场的一条巡回路线。现在的目标:要求合理安排行车路线, 使总空驶里程最短, 并满足2个条件:每辆车每天的行驶里程小于其最大容许行驶里程;每个重载点都得到服务, 并且满足其需求车数。

车辆分配作业顺序不同, 总空驶里程也会随之不同, 因此, 需要解决3个问题:参与完成任务的车辆的数量及分布;参与服务的每一辆车服务的重载点数量;在确定一辆车需要服务的重载点后, 这些重载点之间的排列顺序。

1.2 数学规划模型

设第m个车场有b_m辆车, 其中第k辆车每天的最大行驶距离为D $_{k}^{m}$ , 一般取定值 $\bar{L}$ 。第i个重载点装、卸点之间的距离为d_i, x^mv_ij为整数变量, 表示弧i-j在第m个车场第v辆车的巡回路线上出现的次数, 将车场视为路网上的一个点, 用0表示车场, 则可建立数学模型如下

$\begin{array}{l} \min Ζ = \sum_{m = 1}^{Μ} \sum_{v = 1}^{b_{m}} \sum_{i = 0}^{n} \sum_{j = 0}^{n} d_{i j} x_{i j}^{m v} (1) \\ s . t \sum_{m = 1}^{Μ} \sum_{v = 1}^{b_{m}} \sum_{i = 0}^{n} x_{i j}^{m v} = a_{j} (2) \\ \sum_{m = 1}^{Μ} \sum_{v = 1}^{b_{m}} \sum_{j = 0}^{n} x_{i j}^{m v} = a_{i} (3) \\ \sum_{i = 1}^{n} x_{i p}^{m v} - \sum_{j = 1}^{n} x_{p j}^{m v} = 0 (4) \\ \sum_{i = 1}^{n} d_{i} (\sum_{j = 1}^{n} x_{i j}^{m v}) + \sum_{i = 0}^{n} \sum_{j = 0}^{n} d_{i j} x_{i j}^{m v} \leq \bar{L} (5) \end{array}$

$\sum_{i = 1}^{n}$ x^mv_i0≤1 (6)

$\sum_{j = 1}^{n}$ x^mv_0j≤1 (7)

上述模型中, 式 (1) 为目标函数, 即求总空驶里程, 并使其最小;式 (2) 保证第j个重载点到达车次数与其需求车次数相等;式 (3) 表明从第i个重载点发出的车次数与其需求车次数相等;式 (4) 表明每一重载点发、到车平衡;式 (5) 保证每辆车行驶路径长度不超过每天的最大容许行驶距离;式 (6) 保证车辆回到车场;式 (7) 保证车辆从车场出发。

2. 模型求解的图上作业法

本算法不考虑车场车辆数限制, 利用贪婪算法的原则构造初始解, 再对初始解进行优化, 最后对解进行可行化处理, 得到满意解。

2.1 构造初始解

在这里不考虑车场可以派出空车数的限制, 仅考虑每辆车的行驶距离限制, 按“抄近路”的原则将n个重载点分配给m个车场, 其步骤如下。

(1) 从各车场到重载点距离矩阵中找出距离最小的发车场k_s和重载点k₁ (如果有相同的, 则任选其一, 这里选取下标最小的) 。

(2) 从k₁出发, 寻找距离k₁最近的重载点k₂, 依此方法直到k_p, 使线路长度最大程度接近 $\bar{L} ‚$ 寻找离k_p最近的车场k_e, 则k_s→k₁→k₂→…→k_p→k_e为一条行车路线π, 其发车场为k_s, 收车场为k_e, 计算其中第j个重载点在这条行车路线上出现的次数c_j, 则这条路线的发车数为

$t = \min {[\frac{a_{k_{1}}}{c_{1}}], [\frac{a_{k_{2}}}{c_{2}}], \dots, [\frac{a_{k_{p}}}{c_{p}}]}$

(3) 计算各重载点还需要的车次数a_p=a_p-t (p∈π) , 如果各重载点还需要的车次数均为0, 则找到初始解, 否则转 (1) , 依此方法继续寻找下一条行车路线。

2.2 解的修正

对行车路线进行调整, 使其进一步优化。在此使用2-交换和or-交换法^[7,8]。对线路π_k上的点按其在线路上的次序编号, 分别表示为1, 2, …, i, …, k_t。

2.2.1 2-交换

对线路段{i-1, i}, {i, i+1}, {j-1, j}, {j, j+1}计算

${\begin{cases} z z = d_{i - 1, i} + d_{i, i + 1} + d_{j - 1, j} + d_{j, j + 1} \\ z z^{'} = d_{i - 1, j} + d_{j, i - 1} + d_{j - 1, i} + d_{i, j + 1} \end{cases}$

当zz′<zz时, 则交换i和j的位置, 组成新的路段{i-1, j}, {j, i+1}, {j-1, i}, {i, j+1}, 见图3。

图 3 2-交换

Figure 3. Interpretation for 2-opt

下载: 全尺寸图片幻灯片

2.2.2 or-交换

考虑一个点在另外2个点间重新定位的or-交换, 即点i在点j和j+1中定位, 线路段{i-1, i}, {i, i+1}, {j, j+1}由线路段{i-1, i+1}, {j, i}, {i, j+1}所代替。

当移去i时, 目标值降低

$z z = d_{i - 1, i} + d_{i, i + 1} - d_{i - 1, i + 1}$

当把i置于j, j+1之间时, 目标值增加

$z z^{'} = d_{j, i} + d_{i, j + 1} - d_{j, j + 1}$

当zz<zz′时, 交换有利, 见图4, 实现步骤如下。

(1) 对当前解的各条线路按照每条线路的空驶距离从大到小的顺序排列, 从空驶里程最大的线路开始, 依次将其中的重载点在其他线路上进行定位, 即进行or-交换。

(2) 对当前解的各条线路进行2-交换。

(3) 验算各条线路是否满足最大行驶里程的限制, 若满足, 结束;否则, 将超过部分重新安排线路。

图 4 or-交换

Figure 4. Interpretation for or-opt

下载: 全尺寸图片幻灯片

2.3 解的可行化

由于上面得到的解不一定满足各车场发车数的限制, 即解不一定可行, 需要进一步调整以满足其约束条件, 其步骤如下。

(1) 计算各车场的发车数是否小于 (或等于) 其空车数, 若满足, 结束;否则继续下一步。

(2) 选出一条不满足约束的路线, 从尚有空车的车场中选出与该路线第一个重载点最近的车场作为发车场, 依次进行, 直到满足各车场发车数限制。

(3) 计算各条路线是否满足车辆最大行驶距离约束, 若满足, 结束;否则, 转第 (2) 对解进行修正。

2.4 算法的讨论

此算法是根据贪婪算法的原理设计的一套启发式算法, 将目标的优化置于求解的各个阶段, 以达到解的逐步优化和可行化。

(1) 对解进行修正时, 并非所有的交换都生成可行解, 因此可行的交换最多不超过 $\sum_{i = 1}^{n} a_{i} (\sum_{i = 1}^{n}$ a_i+1) 次, 其时间复杂性为O (n²) 。

(2) 对解进行可行化处理时, 最多进行m $\sum_{i = 1}^{n}$ a_i次运算, 其时间复杂性为O (mn) 。

一般情况车场数m小于任务数n, 因此整个算法的时间复杂性为O (n²) 。

算法的关键在于解的修正时找出最有利, 即目标值降低最大、最快的交换方式。可利用禁忌搜索、遗传算法等优化方法辅助实现。

3. 算例

对文献[7]中的算例进行计算, 已知有6个重载点、3个车场, 各重载点之间以及与车场之间的距离见表1, 取 $\bar{L} = 90$ km, 各重载点内的重载行驶里程均为10 km。各重载点所需车次数以及各车场可提供空车数见表2。

表 1 各车场与重载点及重载点之间的距离 /km

Table 1. Distances from full loads sites to each depot and other sites

i	j
i	车场1	车场2	车场3	1	2	3	4	5	6
车场1	-	-	-	8	1	3	5	4	6
车场2	-	-	-	7	2	7	9	11	2
车场3	-	-	-	4	3	2	5	7	8
1	2	3	4	3	6	9	2	3	5
2	1	5	7	11	8	7	1	4	10
3	8	6	2	12	3	8	9	5	6
4	4	9	5	4	10	3	8	6	7
5	3	1	6	3	2	4	7	1	9
6	2	10	9	6	7	8	9	10	1

下载: 导出CSV

| 显示表格

表 2 各重载点所需车次数及各车场空车数

Table 2. Vehicle demands of every full loads site and empty car available in each depot

i	1	2	3	4	5	6	车场1	车场2	车场3
a_i	20	15	30	10	8	9	20	30	40

下载: 导出CSV

| 显示表格

表 3 初始解

Table 3. Initial solutions

线路标号	行车路线	空驶里程	总里程
π₁-π₅	车场1-2-4-3-2-4-3-2-车场1	16	86
π₆	车场2-6-6-6-6-6-6-6-车场1	10	80
π₇	车场2-6-6-1-1-1-1-车场1	20	80
π₈	车场3-3-5-5-5-5-5-5-车场2	13	83
π₉	车场3-3-5-5-1-1-1-车场1	19	79
π₁₀-π₁₂	车场3-3-3-3-3-3-车场3	32	86
π₁₃	车场3―3-3-3-1-1-车场1	35	85
π₁₄-π₁₅	车场3-1-1-1-1-1-1-车场1	21	81
π₁₆	车场3-1-1-车场1	9	29

下载: 导出CSV

| 显示表格

3.1 构造初始解

以“抄近路”的原则构造的初始解见表3, 此时, 总空驶里程为324 km, 共使用16 veh车。

3.2 解的修正

利用2-交换和or-交换法对构造的初始解进行优化, 得满意解, 其行车路线见表4。

表 4 满意解

Table 4. Satisfactory solutions

线路标号	行车路线	空驶里程	总里程
π₁-π₅	车场3-3-2-4-3-2-4-3-车场3	18	88
π₆	车场1-2-5-5-5-5-5-5-车场2	11	81
π₇	车场1-2-5-5-3-2-3-车场3	22	82
π₈	车场2-6-6-6-6-6-6-6-车场1	10	80
π₉	车场2-6-6-1-1-1-1-车场1	20	80
π₁₀	车场2-2-3-2-3-3-车场3	25	75
π₁₁-π₁₂	车场3-3-3-3-3-3-车场3	32	86
π₁₃-π₁₄	车场3-1-1-1-1-1-1-车场1	21	81
π₁₅	车场3-1-1-1-1-车场1	15	45

下载: 导出CSV

| 显示表格

此时, 总空驶里程为299 km, 共使用15 veh车, 车场1发出2 veh, 车场2发出3 veh, 车场3发出10 veh空车, 与文献[7]给出的解 (292 km, 15 veh) 接近。

3.3 解的可行性

由于各车场发车数均小于其空车数, 因此此解可行。

4. 结语

合理调度车辆是降低生产成本、提高经济效益的重要手段。本文针对满载情况下多车场车辆优化调度问题, 提出了车辆调度的优化模型, 并构造了求解该问题的启发式算法。试验结果表明:利用该算法可以有效地求得多车场车辆调度问题的满意解。

图 1 MDVS运输网络

Figure 1. MDVS transportation network

下载: 全尺寸图片幻灯片

图 2 重载点及其之间的距离

Figure 2. Full loads sites and distance from each other

下载: 全尺寸图片幻灯片

图 3 2-交换

Figure 3. Interpretation for 2-opt

下载: 全尺寸图片幻灯片

图 4 or-交换

Figure 4. Interpretation for or-opt

下载: 全尺寸图片幻灯片

表 1 各车场与重载点及重载点之间的距离 /km

Table 1. Distances from full loads sites to each depot and other sites

i	j
i	车场1	车场2	车场3	1	2	3	4	5	6
车场1	-	-	-	8	1	3	5	4	6
车场2	-	-	-	7	2	7	9	11	2
车场3	-	-	-	4	3	2	5	7	8
1	2	3	4	3	6	9	2	3	5
2	1	5	7	11	8	7	1	4	10
3	8	6	2	12	3	8	9	5	6
4	4	9	5	4	10	3	8	6	7
5	3	1	6	3	2	4	7	1	9
6	2	10	9	6	7	8	9	10	1

下载: 导出CSV

表 2 各重载点所需车次数及各车场空车数

Table 2. Vehicle demands of every full loads site and empty car available in each depot

i	1	2	3	4	5	6	车场1	车场2	车场3
a_i	20	15	30	10	8	9	20	30	40

下载: 导出CSV

表 3 初始解

Table 3. Initial solutions

线路标号	行车路线	空驶里程	总里程
π₁-π₅	车场1-2-4-3-2-4-3-2-车场1	16	86
π₆	车场2-6-6-6-6-6-6-6-车场1	10	80
π₇	车场2-6-6-1-1-1-1-车场1	20	80
π₈	车场3-3-5-5-5-5-5-5-车场2	13	83
π₉	车场3-3-5-5-1-1-1-车场1	19	79
π₁₀-π₁₂	车场3-3-3-3-3-3-车场3	32	86
π₁₃	车场3―3-3-3-1-1-车场1	35	85
π₁₄-π₁₅	车场3-1-1-1-1-1-1-车场1	21	81
π₁₆	车场3-1-1-车场1	9	29

下载: 导出CSV

表 4 满意解

Table 4. Satisfactory solutions

线路标号	行车路线	空驶里程	总里程
π₁-π₅	车场3-3-2-4-3-2-4-3-车场3	18	88
π₆	车场1-2-5-5-5-5-5-5-车场2	11	81
π₇	车场1-2-5-5-3-2-3-车场3	22	82
π₈	车场2-6-6-6-6-6-6-6-车场1	10	80
π₉	车场2-6-6-1-1-1-1-车场1	20	80
π₁₀	车场2-2-3-2-3-3-车场3	25	75
π₁₁-π₁₂	车场3-3-3-3-3-3-车场3	32	86
π₁₃-π₁₄	车场3-1-1-1-1-1-1-车场1	21	81
π₁₅	车场3-1-1-1-1-车场1	15	45

下载: 导出CSV

参考文献(8)

[1]	Clarke G, Wright J.Scheduling of vehicles from a central depot to number of delivery points[J].Opns.Res., 1964, 12(4):12-18. https://www.cnki.com.cn/Article/CJFDTOTAL-GLXB202007018.htm
[2]	Gillett B E, Miller L R.A heuristic algorithm for the vehicle dispatch problem[J].Opns.Res., 1974, 22(4):340-349. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC202109012.htm
[3]	Fisher M L, Jaikumar R.A generalized assignment heuristic for vehicle routing[J].Networks, 1981, 11(2):109-124. https://www.cnki.com.cn/Article/CJFDTOTAL-TDYT202102003.htm
[4]	JIANG Da-li, YANG Xi-long, DU Wen, et al.A study on the genetic algorithm for vehicle routing problem[J]. Systems Engineering-Theory and Practice, 1999, 19(6):40-44.(in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL202001012.htm
[5]	JIN Hai-he, CHEN Jian, ZHAO Chun-jun.Optimization model for a distribution network and its solution algorithm[J].Journal of Tsinghua University(Science&Technology), 2002, 42(6):739 -742.(in Chinese) doi: 10.3321/j.issn:1000-0054.2002.06.008
[6]	HANG Sheng-ce, LI Huai-zu.The generalized assignment model and its decoosition algorithm of multipledepot vehicle scheduling problem(MDVSP)[J].Journal of Xi'an Jiaotong University, 1997, 31(12):111-115.(in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DGJS202103013.htm
[7]	GUO Yao-huang, LI Jun.Vehicle routing with full loads[J]. Journal of Systems Engineering, 1995, 10(2):106-118.(in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL202101017.htm
[8]	刑文训, 谢金星.现代优化计算方法[M].北京:清华大学出版社, 1999.

施引文献

资源附件(0)

访问统计

点击查看大图

图(4) / 表(4)

计量

文章访问数: 473
HTML全文浏览量: 148
PDF下载量: 519
被引次数: 0

0. 引言
1. 多车场车辆调度数学模型
1.1 问题描述及运输网络模型
1.2 数学规划模型
2. 模型求解的图上作业法
2.1 构造初始解
2.2 解的修正
2.3 解的可行化
2.4 算法的讨论
3. 算例
3.1 构造初始解
3.2 解的修正
3.3 解的可行性
4. 结语

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

多车场车辆优化调度模型及算法

作者简介:
李臻(1980-),男,河南荥阳人,中南大学硕士研究生,从事运输规划与管理研究.

计量