基于快递业物流的优化调度问题研究

刘艳秋，郭长亮

摘 要：现代化物流分支广泛，本文针对现代化物流业中的快递业物流优化调度问题，建立了为使任务成本最小的优化模型，根据快递业物流特点，基于遗传算法利用其中。利用真实的用例来验证遗传算法在快递业物流调度中的可行性。

关键词：快递业；优化模型；遗传算法

0 引言

快递业作为现代物流业的一个分支，在电子商务市场的发展下，快递业物流也得到迅猛发展。车辆调度问题（Vehicle scheduling Problem，简称VSP）作为物流业的核心问题，各个领域专家学者提出了不同的研究方案[1，2]。上个世纪中叶，Dantzing和Ramser最早提出了商旅问题[3]，标志着VSP理论的正式成立。本文从物流业特点出发，从快递业物流配送物件相对较小，快递员（配送人员）能力限制，及客户点分散等的综合现状下分析，找到最优的调度方案。

VSP问题属于NP-hard问题，在规模较小的情况下可以使用精确算法求出最优解[4]，而启发算法则在较大的规模下有着非常重要的作用[5，6]。目前大量使用的智能算法有模拟退火算法、禁忌搜索算法、蚁群算法等智能优化算法，考虑到实际和本文的模型特点，采用遗传算法对问题进行求解。

1 问题描述和数学模型的确立

快递业车辆调度问题可描述为：有N个客户点，并且每个客户点的配送量及位置已知，快递员k从快递站点出发到达这批客户点。快递员在配送任务完成后，返回快递站点。在选择和确定实际配送路线和完成配送货任务过程中，使得总费用最小。

用1，2，3，…，M表示快递员的编号，令m={1，2，3，…，M}； R表示m的行驶速度，设为一常值；设每个快递物件重量大小为1（由于快递物件重量相对较小）；Nmax表示为快递员在一次配送任务的最大工作量（件数）；eij表示客户点i与j之间所需的行驶成本（指距离，费用之和等）；设行驶单位距离成本为q，设q为1，eij与客户i到客户j的行驶的距离dij成线性关系；p0表示快递员配送快递物件的每件提成，为固定值。

设决策变量为：x■■=1 快递员m从i离开后前往j0 否则；

模型描述为： min■■■e■+p■x■■ （1）

st.■■x■■=1，i=1，…，N，j≠i （2）

■■x■■=1，j=1，…，N，i≠j （3）

■x■■■x■■=1，m=1，…，M，i=0 （4）

■x■■≤N■，m=1，…，M，j=1，…，N （5）

e■=qd■=d■ i，j=0，1，…，N （6）

x■■∈0，1 i，j=0，1，…，N， i≠j （7）

式（1）表示目标函数，即最小任务成本。

式（2）（3）确保每个客户只能被一位快递员服务一次。

式（4）确保所有的快递员都从快递站点出发且最终都返回快递站点。

式（5）确保每次快递员的任务量不超过快递员的最大工作承受能力，即快递员容量限制为Nmax。

式（6）i，j之间行驶成本计算说明。

式（7）确保决策变量为0～1的决策变量。

2 模型求解

快递业车辆调度问题：有N个客户点，并且每个客户点位置及配送量已知，有M个快递员，快递员从快递站点出发，配送完货物后回到快递站点，由于快递员最大工作能力限制，所以每次任务快递员配送货物有限。

本文属于NP-hard问题，遗传算法[7]对上文模型求解具有良好的特性。Malmborg[8]、Baker Barrie[9]等人在遗传算法应用于车辆调度问题进行了研究。本文也采用遗传算法对上述模型进行求解。具体内容如下：

2.1 染色体编码

染色体结构的设计对遗传算法是至关重要的，本文的染色体编码由三部分组成。第一部分是快递员编号，第二部分为客户点编号，第三部分为快递站点编号（设置为0）。

例如本文中染色体的S结构可表示为：

S：（1415202360）

表示：编号为1的快递员从快递站点出发，经过的路径为客户点4→客户点1→客户点5→客户点2→快递站点0；编号为2的快递员从快递站点出发，经过的路径为客户点3→客户点6→快递站点0。使用的快递员数为2个。

2.2 种群初始化

初始种群包括多条染色体，每条染色体中客户点的顺序随机打乱，再根据快递员能力限制插入快递员编号。染色体长度是根据客户点是由使用的快递员数和客户点数决定的。

2.3 选择

本文采用轮盘赌（roulette wheel）的方法，依照适应度函数值，从群里中找到比较适应环境的个体。

2.4 交叉

根据适当的交叉率选择选择出需要交叉的种群， 为了说明交叉过程，示例如下：

任意选出两个父体

1→4→1→5→2→0→2→3→6→0

1→3→2→5→1→0→2→6→4→0

经过交叉，互换两个基因段，去掉快递员编号和快递站点编号，得到两个子体为

6→1→5→2→2→6

3→3→5→1→4→4

按照这种交叉的操作方法，一条染色体中会出现相同的基因，那么就要把没有进行交换操作的基因段的重复基因与另外一条染色体按顺序进行交换，可得到

6→1→5→3→2→4

2→3→5→1→4→6

根据快递员能力约束，随机插入快递员编号及快递站点编号，可得到

1→6→1→5→3→0→2→2→4→0

1→2→3→5→0→2→1→4→6→0

2.5 变异

按照生物进化理论，在繁殖过程中，基因会发生一定概率的出错，本文的变异操作过程是随机选取两个客户点交换位置，加入判断，比较与前代染色体的适应度，改良则保留，否则舍弃，一直循环下去，知道产生所能达到最好的染色体为止。

2.6 适应度的运算

由遗传算法得到的每条染色体，本文的适应度函数取总目标值。

■■■e■+p■x■■

从上式适应函数可以看出，当适应函数值越低，则染色体越优。

3 算例

假设某一快递站点有3个快递员，每个快递员一次任务最大工作能力为10件货物，在某一时刻有16个需要服务的客户点，客户点之间的距离分别如下面的表1所示。要求安排快递员行驶路线使总费用最小。

对优化目标应用本文的方案进行求解，可得行驶路线具体如下：

编号为1的快递员：2→1→6→11→16→7→0

编号为2的快递员：5→9→10→14→15→0

编号为3的快递员：4→8→12→13→3→0

最终求得最小花费（目标函数值）Bestfitness=615

4 结论

本文对快递业调度优化问题进行了描述，为了求解该问题，找到适合本文问题的启发算法-遗传算法，该算法直观、简便、易操作。利用遗传算法求出配送成本最小的路径。本文的设计思想更贴合实际生活中快递业调度问题，此模型可以灵活运用到实际问题中去。

参考文献：

[1]李军，郭耀煌. 物流配送车辆优化调度理论与方法[M].北京： 中国物资出版社，2001.

[2]王海滨，孙永道，等.多车场多目标开放式物流配送车辆调度问题的研究[A].计算机测量与控制.2010.18（12）.

[3]Dantizig G，Ramser J. .The truck dispatching proble[J].Management Science，1959，6：80～91.

[4]Toth P， Vigo D. Exact Solution of the Vehicle Routing Problem[M]. In Fleet Management and Logistics. Dordrecht： Kluwer， 1998.1-31.

[5]Laporte G. The vehicle routing problem： An overview of exact and approximate algorithms[J]. European Journal of Operational Research， 1992，59：345-358.

[6]Laporte G， Gendreau M，Potvin J Y， et al.Classical and moderm heuristicsfor the vehicle routing problem[J]. International Transactions in Operational Research， 2000，7：285-300.

[7]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.

[8]Malmborg，Charles.Genetic algorithm for service level based vehicle scheduling[J].European Journal of Operational Research， 1996，93（1）：121-134.

[9] Baker Barrie M， Ayechew M A. Agenetic algorithm for the vehicle routing problem[J]. Computer & Operations research， 2003，30：787-800.

基金项目：辽宁省科学技术计划项目（2013216015）；沈阳市科学技术计划项目