带二维装箱约束的团队定向问题模型及优化算法

彭 勇，宋其勤

(重庆交通大学 交通运输学院，重庆 400074)

带二维装箱约束的团队定向问题模型及优化算法

彭 勇，宋其勤

(重庆交通大学 交通运输学院，重庆 400074)

研究了在车辆服务资源有限、货物有特殊装载要求和其他因素影响下，为了能获得最大效益而采取特殊物流配送的问题——带二维装箱约束的团队定向问题。在对该问题进行明确定义基础上，建立了相应的数学模型；针对模型特点，设计了以遗传算法为框架，利用基于BLF的算法确保二维装箱约束的模型启发式算法。数值算例验证了算法的有效性。

交通运输工程；团队定向问题；二维装箱约束；遗传算法

0 引 言

团队定向问题(team orienteering problem, TOP)是一类特殊的车辆配送路径优化问题[1-2]，它寻求的是收益最大化。比如，在配送服务中，对每位服务客户，企业将根据配送服务情况获取一定收益(比如送货费)，但由于客户配送时间要求、车辆不足等各方面条件限制，企业无法为所有客户提供服务，此时，企业面临的决策将是如何充分利用自身能力，获取更多收益的问题。

车辆路径问题作为网络优化问题中最基本的问题之一，一直受到学者的关注。彭勇等[3-4]在综合考虑车辆行驶速度随时间、路段不同而变化的特点，及车辆为多条路线上的客户提供服务时对车辆路径优化的影响后，分别运用粒子群算法以及Dijkstra-GA算法对路径进行优化；李毅等[5]针对车辆路径问题中单仓库非满载这一基本类型的具体特性，设计了一种混沌粒子群算法，较快得出最优路径。在物流配送实践中，不能只考虑路径最优，部分货物由于易损、易碎等原因，导致装车货物可能无法叠放。目前，有学者在对所有客户均需要提供服务的车辆配送路径优化中考虑该约束条件[6]。但对于团队定向问题这类不需要对所有客户提供服务的特殊车辆配送路径优化问题，尚未发现有文献考虑该约束条件。即，笔者将研究带二维装箱约束的TOP(TOP with two-dimensional loading constraints，2L-TOP)[7-9]。该问题中，由一定数量的车辆为一定数量客户提供服务，每辆车在进行任务安排时必须满足车辆装载约束(二维装箱约束、车辆最大载重约束)和车辆最大行驶距离约束。一旦某辆为某位客户提供服务，企业将获得相应收益，而其他车辆将不再为该客户重复提供服务，优化目标为总收益最大化。由于团队定向问题只服务部分客户，目标为收益最大化的特点，其优化算法设计与一般车辆路径问题有差异[10-13]，而笔者所提出的问题增加了二维装箱约束，其优化算法需要结合问题特点重新设计。

1 2L-TOP数学描述

在数学描述中，令G=(V，E)；顶点集V={1,2,…,n}，其中：1,n为同一点(车辆从1出发，结束于n)表示车场，其余为客户需求点；E={(i,j)|i,j∈V}为边集；顶点间距离为Dij；每个客户点i对应一个收益wi(当该客户所有物品均由一辆车配送到时获取该收益)；定义Ai为客户点i所要求配送的mi个矩形物品集合；Ai中物品总重di。Ai中物品m(Iim)为底面投影为lim(物品水平方向长度)×wim(物品垂直方向长度)的矩形(在以下数学模型中会增加一下标k表示该物品放入对应车辆)。

令车厢俯视图(车头在下)左下角为坐标原点，水平向右、垂直向上为坐标轴。设物品Iim左下角坐标为(vim，him)(在以下数学模型中会增加一下标k表示该物品放入对应车辆)。令K={1,2,…,vh}为车辆集合；Qk为车辆k的最大载重量，k∈K；Dmax为单车的最大行驶距离。

式中：i=2,3，…, (n-1)；k∈K；

式中：i=1,2,…,n；j=1,2,…,n；k∈K。

2L-TOP数学描述如下：

(1)

(2)

(3)

(4)

(5)

(6)

0≤vimk≤W-wimk, ∀i∈{2,3,…,n-1},m∈{1,2,…,mi},k∈K

(7)

0≤himk≤L-limk, ∀i∈{2,3,…,n-1},m∈{1,2,…,mi},k∈K

(8)

himk+limk≤hi′m′k, ∀i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(9)

vimk+wimk≤vi′m′k, ∀i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(10)

vimk≥vi′m′k, ∀i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(11)

himk+limk≤hi′m′k, ∀i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(12)

hi′m′k+li′m′k≤himk, ∀i,i′∈{2,3,…,n-1},m∈{1,2,…,mi},m′∈{1,2,…,mi′},k∈K,i≠i′

(13)

(14)

上述整数线性规划模型的含义如下：

式(1)给出模型优化目标为总收益最大化；式(2)、式(3)表示每一辆车均从1出发，止于n；式(4)表示每辆车到达某点次数等于离开其点次数；式(5)表示每点最多由一辆车提供一次服务；式(6)为车辆载重量限制；式(7)、式(8)表示每条路径上物品以固定方向都能装入车内；式(9)、式(10)表示物品不能相互叠放；式(11)～(13)保证装箱物品能按序不受阻挡以物品装入方向直线移进移出；式(14)为行驶距离限制。

2 2L-TOP算法设计

针对所给数学模型，笔者设计了以遗传算法作为算法框架，利用基于BLF的算法确保二维装箱约束的2L-TOP启发式算法(BLF-GA算法)。

2.1 编 码

采用随机小数编码形成个体[14]。比如：可能服务客户10个，可提供的最大车辆数K为4辆，则个体长度为：N=10+4-1=13。假设某一个体为[0.51 0.23 0.67 0.59 0.47 0.56 0.58 0.92 0.73 0.32 0.49 0.08 0.70]，解码时，首先根据个体各基因值大小升序排列形成对应基因位置序号的一个排列[6 2 10 9 4 7 8 13 12 3 5 1 11]。将大于10的数字以0替换，进一步解码为[6 2 10 9 4 7 8 0 0 3 5 1 0]。然后，以0为路径分割点，进一步解码形成2条路径(0代表车场)如下：0→3→5→1→0；0→6→2→10→9→4→7→8→0。

但以上形成的只是可能服务路径，实际服务路径还需满足车辆装箱约束(调用基于BLF的二维装箱算法检验)、载重约束和行驶里程约束。从最后提供服务的客户开始依次向前放弃不满足车辆装箱约束、载重约束及行驶里程约束的客户，最终形成满足约束条件的实际服务路径。

2.2 初始种群

采用“随机”的方法生成初始种群。

2.3 适应度评价

目标函数为适应度函数。

2.4 选择操作

轮盘赌法和精英保留策略的结合。

2.5 交 叉

采用部分映射的方法，从种群中随机抽取两个个体形成一组。对每组个体，若随机生成数不大于交叉概率pc，则随机交叉互换；否则，该组个体不进行交叉操作。经过交叉操作或未经过交叉操作的个体构成新种群的个体。不断重复此过程，直到该过程形成的个体数量达到群体规模一半为止。如下所示，个体a，b的[5，10]段互换。

个体a：[ 0.52 0.18 0.60 0.55 0.46 |0.50 0.77 0.90 0.71 0.31 | 0.49 0.17 ]

个体b：[ 0.31 0.05 0.26 0.58 0.43 |0.86 0.31 0.73 0.42 0.39 | 0.83 0.22 ]

↓↓

个体a′：[ 0.52 0.18 0.60 0.55 0.46 |0.86 0.31 0.73 0.42 0.39 | 0.49 0.17 ]

个体b′：[ 0.31 0.05 0.26 0.58 0.43 |0.50 0.77 0.90 0.71 0.31 | 0.83 0.22 ]

2.6 变 异

对种群每一个体，若随机生成数不大于变异概率pm，则随机对个体某一位置的数值重新随机生成，形成新个体；否则，不进行变异操作。如下所示，假设个体a随机选取位置为5，对应0.45，随机变异为0.86，形成新个体a′。

个体a：[ 0.31 0.27 0.65 0.56 0.450.58 0.77 0.84 0.73 0.33 0.85 0.72 ]

↓↓

个体a′：[ 0.31 0.27 0.65 0.56 0.860.58 0.77 0.84 0.73 0.33 0.85 0.72 ]

算法流程如下：①参数初始化；②随机产生初始种群；③若满足迭代次数等于最大迭代次数，转到⑨，否则转到④；④对种群个体解码，计算种群个体适应值；⑤轮盘赌生成新种群；⑥交叉、变异操作；⑦采用精英保留策略，得到子代种群；⑧迭代次数增加一次，转到③；⑨取种群最优的适应值即为最优收益，对应个体解码后形成最优方案。

3 基于BLF的二维装箱算法设计

针对文中模型装箱约束条件，设计了基于BLF[9-10]的二维装箱算法。

假设某几位客户配送物品形成某个装入序列，已装入4件物品，如图1。首先确定这4件物品左下点(某品左下点是由该物品矩形上线段上的左下点和右线段上的左下点组成)，方法如下：

1)物品上线段上的左下点为物品的上线段以右点为原点向左延伸与该物品的左边物体第一次相交的点或与车厢左侧厢壁相交的点；若该点在某物体的下线段上，则该物品在上线段上没有左下点(物品3的上线段在物品4的下线段上，因此，物品3的上线段无左下点)，如图1。

图1 物品上线段上的左下点Fig.1 Left lower point on the line segment of items

2)物品右线段上的左下点为物品右线段向下延伸与其下方物品第一次相交的点；若该点在其他物品的左线段上，则该物品在右线段上没有左下点(物品1的右线段向下延伸交点在物品2的左线段上，物品2的右线段向下延伸交点在物品3的左线段上，因此，物品1、2右线段都无左下点)，如图2。

图2 物品右线段上的左下点Fig.2 Left lower point on the right line segment of items

把所有左下点按照左下点靠近车头距离升序排序，如图3。在放下一个物品时，首先选择升序排列的第一个左下点放，若能放下，就将该物品放在此处，若不能，依次选择升序排列的下一个左下点放，直到找到能放下该物品的左下点。判断在某左下点能否放下该物品的依据是比较该左下点对应的区间长度与该物品的长度，若前者大，则能放下该物品，否则就不能。

图3 左下点排序Fig.3 Sorting of left lower points

计算某物品左下点对应的区间长度方法：以该物品左下点为原点，向右做一条平行靠近车头车厢壁的射线，当该射线与其他物品的左线段相交时或与车厢右壁相交时，则之间的距离为该物品左下点对应的区间长度，如图4中的左下点1，2，3，4，5。

图4 物品左下点对应的区间长度Fig.4 Corresponding interval lengths of left lower points of items

按以上方法装货时，可能不满足模型约束。如图5，物品4下方形成一空隙。当放置下一个物品5时，按以上放置方法，物品5可能被放入物品4下方空隙。但实际装车过程中，物品5可能由于物品4旁边空间不够，受到阻挡，无法放入；或者需要向下然后左移才能放入。两种情况均不满足模型约束。

图5 物品4不覆盖物品3Fig.5 Item 3 not covered by item 4

笔者在算法中采用覆盖方法避免发生此种情况，算法中每放入车厢一件物品后，均会首先采取如图6和图7的覆盖操作，形成已放入车厢新的虚拟物品；然后再采取同样方法寻找已放入车厢物品左下点，继续按序放入物品。

图6 物品4完全覆盖物品3Fig.6 Item 3 completely covered by item 4

图7 物品4部分覆盖物品3Fig.7 Item 3 partly covered by item 4

图6中，物品4完全覆盖物品3，则把物品4和3合成，作为物品4，属于物品3的信息都变成0。图7中，物品4部分覆盖物品3，则把覆盖的部分合成到物品4里面，物品3则减少覆盖的部分。

覆盖处理的作用可从图8、图9看出。当采取覆盖处理后，物品1放置位置从图8所示位置变为图9所示位置。在装卸物品1时可沿装车方向直接移进移出，从而在装卸中减少物品发生碰撞可能及装卸时间与装卸成本。

图8 物品1处于物品2，3左侧空隙Fig.8 Item 1 is on the left side of space of item 2, 3

图9 覆盖保证物品1不会放入物品2，3左侧空隙Fig.9 Coverage ensuring that item 1 will not be put on the left side of space of item 2, 3

4 数值算例

算法采用MATLAB实现。所有计算在操作系统Windows7、配置为Inter Core i3-2330 M、2.20 GHz、4.00 GB内存电脑上完成。

由于尚未发现2L-TOP研究文献，难以直接验证本文算法有效性。笔者采用调整参数的方式将问题变为已有研究文献的TOP或2L-CVRP，间接验证本文算法有效性。TOP选取Benchmark算例p1.2，p1.3，p1.4，2L-CVRP选取Iori提出的Benchmark算例E016-03m.dat，E021-04m.dat测试算法有效性。

在Chao测试算例p1.2，p1.3，p1.4中，为能应用本文算法，增加车长40和宽20，载重为90，物品长宽均为1，物品重量为1。由于所有物品为标准正方形且面积相对车厢面积极小，相当于无装箱约束，同样道理，物品重量远小于车辆最大载重量，相当于无装载重量约束。因此，在增加参数后，其问题与Chao测试算例无区别，计算结果可比较。利用本文算法，每个类别各计算10次，选取最好结果如表1。

表1 文中算法在Chao测试算例的结果

Chao所有测试算例给出的已有TOP算法计算用时约为20～40 s，笔者所给算法计算用时约为40～55 s，文中算法用时略高；文中计算结果与Chao测试算例所给结果基本相同(图10)。文中算法增加了物品属性(长、宽、重量)，算法中嵌入了装箱算法，算法运行时间增加应在预料之中。

图10 p1.2.b配送路径方案和算法优化过程Fig.10 Scheme of distribution route and process of algorithm optimization for p1.2.b

综合来看，文中算法在最优结果和效率上可以接受，说明文中算法是有效的。

在Iori测试算例中，单车行驶最大距离设置成无限大，使用笔者提出的算法，得到最优路径，然后得到这条路径的总长度，再与算例结果进行对比，如表2。表2中数据是2L-CVRP算例E021-04m.dat(NO.3)和E016-03m.dat(NO.1) 中的CLASS1。由于行驶距离无限制，所有客户均会被服务，总收益也自然达到最大值(所有客户收益总和)。因此，需要对本文算法适应函数调整为总路径长度的倒数，即优化目标调整为最小化总路径长度。

表2 文中算法在Iori测试算例的验算结果

注：δ1=(文中算法优化路径长度-测试算例所给优化路径长度)/测试算例所给优化路径长度。

文中算法计算结果较为接近算例所给结果。不一致主要是由于文中算法是针对文中模型设计，相对于专门针对2L-CVRP设计的算法用于2L-CVRP，文中算法计算结果有一定差异应在预料之中。但计算结果较为接近，说明文中算法是有效的。

利用算例E016-03m.dat(NO.1)数据，增加点的收益，形成2L-TOP。随机生成15个点的收益为：V=[10 22 10 12 18 20 11 18 15 14 35 18 23 16 20]。令单车最大行驶距离=5，每个类别各计算10次，结果如表3(表中数据来自2L-CVRP算例的中的E016-03m.dat(NO.1)，包含5种类别)。图11为使用文中算法计算10次的结果。

表3 文算法在Iori测试算例的结果

注：装载率1=最优路径中客户物品的面积/(车辆数×车辆面积)；装载率2=所有客户物品的面积/(车辆数×车辆面积)；δ2=(装载率2-装载率1)/装载率2。

从表3可见，计算时间随物品增多成线性增长。从图11可见，装载率高，收益不一定高，可能的原因是个别客户的物品占车辆较多空间或重量太重，但其支出的服务费用(服务收益)却比较少。

5 结 语

考虑物流配送实践，笔者提出了带二维装箱约束的团队定向问题，建立了该问题的数学模型。根据所建立数学模型特点，设计了BLF-GA算法，利用Iori和Chao数据间接验证了算法有效性。最后，给出了算法数值算例。

[1] CHAO I M, GOLDEN B L, WASIL E A. The team orienteering problem[J].EuropeanJournalofOperationalResearch, 1996, 88(3): 464-474.

[2] VANSTEENWEGEN P, SOURLAU W, OUDHEUSDEN D. The orienteering problem: a survey[J].EuropeanJournalofOperationalResearch, 2011, 209(1): 1-10.

[3] 彭勇,谢禄江,刘松.时变单车路径问题建模及算法设计[J].重庆交通大学学报(自然科学版),2013,32(2):263-266. PENG Yong, XIE Lujiang, LIU Song. Route modeling and algorithm designing of time-dependent single vehicle[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2013,32(2):263-266.

[4] 彭勇,何俊生.实时路网单车多任务物流配送路径优化[J].重庆交通大学学报(自然科学版),2014,33(2):123-125. PENG Yong, HE Junsheng. Route optimization of multi-trip single vehicle based on real time road network[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2014,33(2):123-125.

[5] 李毅,陆百川,刘春旭.车辆路径问题的混沌粒子群算法研究[J]. 重庆交通大学学报(自然科学版),2012,31(4):842-845. LI Yi, LU Baichuan, LIU Chunxu. Research on chaos particle swarm optimization algorithm for vehicle routing problem[J].JournalofChongqingJiaotongUniversity(NaturalScience),2012,31(4):842- 845.

[6] 王征,胡祥培,王旭坪.带二维装箱约束的物流配送车辆路径问题[J].系统工程理论与实践,2011,31(12):2328-2341. WANG Zheng, HU Xiangpei, WANG Xuping. Vehicle routing problem in distribution with two-dimensional loading constraint [J].SystemsEngineeringTheory&Practice, 2011, 31(12): 2328-2341.

[7] BAKER B S, COFFMAN J E G, RIVEST R L. Orthogonal packing in two dimensions[J].SIAMJournalonComputing,1980,9(4): 846-855.

[8] BROWN D J. An improved BL lower bound[J].InformationProcessingLetters,1980,11(1):37-39.

[9] 武晓今,朱仲英.二维装箱问题的一种实现方法[J].微型电脑应用,2003,19(4):20-23. WU Xiaojin, ZHU Zhongying. A method to solve two-dimensional loading problem[J].MicrocomputerApplications,2003,19(4):20-23.

[10] DANG Duc-cuong, GUIBADJ R N, Moukrim A. A PSO-based memetic algorithm for the team orienteering problem[J].ApplicationsofEvolutionaryComputation,2008,4974:649-658.

[11] BOULY H, DANG Duc-cuong, MOUKRIM A. A memetic algorithm for the team orienteering problem[J].ApplicationsofEvolutionaryComputation,2008,4974:49-70.

[12] DANG D C, GUIBADJ R N, MOUKRIM A. An effective PSO-inspired algorithm for the team orienteering problem[J].EuropeanJournalofOperationalResearch,2013,229(2):332-344

[13] KIM B I, LI Hong, ANDREW L J. An augmented large neighborhood search method for solving the team orienreering problem[J].ExpertSystemswithApplications,2013,40(8):3065- 3072

[14] BEAN J C. Genetic algorithms and random keys for sequencing and optimization[J].ORSAJournalonComputing,1994,6(2):154-160.

Model of Team Orienteering Problem with Two-Dimensional Loading Constraint and Its Optimization Algorithm

PENG Yong, SONG Qiqin

(School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, P.R.China)

Taking the limited vehicle service resources, special goods loading requirements and other factors into account, a special logistic problem to maximize the profit — a team orienteering problem with two-dimensional loading constraint was studied. On the base of clear definition of the above problem, a corresponding mathematic model was established. Aiming at the model characteristics, a heuristic algorithm was designed, which took the genetic algorithm as a framework and made use of BLF algorithm to ensure two-dimensional loading constraint model. Numerical studies verify the effectiveness of the proposed algorithm.

traffic and transportation engineering; team orienteering problem; two-dimensional loading constraint; GA

10.3969/j.issn.1674-0696.2016.03.29

2014-10-09；

2015-01-04

彭 勇(1973—)，男，重庆人，教授，博士，主要从事交通运输规划与管理方面的研究。E-mail:pengyong@cqjtu.edu.cn。

U492.3+1

A

1674-0696(2016)03-141-06