图 1自送路径和外包路径的差别
纸质出版日期:2020-07-20,
收稿日期:2019-03-30
扫 描 看 全 文
引用本文
阅读全文PDF
文章提出联合外包策略的定位运输规划模型,以期通过部分车辆任务外包减少物流系统成本。考虑实际运营中的时间窗等限制条件,以及自送和外包运输成本构成,通过联合优化配送中心选址和车辆路径决策,构建了最小化物流网络总成本的模型,包括自营车辆固定成本和可变运输成本、配送中心建设的固定成本,以及外包配送的运输成本。根据问题的特征设计了遗传算法的分段编码方法。通过仿真算例,将所提出的策略与传统全部自送和全部外包运营模式进行比较。结果表明,通过部分车辆任务外包可以有效减少自送的额外成本和配送中心建设成本,从而降低系统成本,在该仿真算例中该策略较完全自送模式成本降低了8.08%,较完全外包模式成本降低了25.03%,最后通过敏感性分析考察了不同外包价格对系统决策的影响。
The rapid development of logistics outsourcing has brought new opportunities for the supply chain integration design. This paper proposes a location routing problem planning model with the outsourcing strategy, with the objective to reduce the logistics system cost via partially outsourcing vehicle tasks. Considering the constraints in actual operation such as time windows, and the composition of self-delivery and outsourcing transportation costs, we develop a model to minimize the total cost of the logistics network by a jointly optimizing the distribution of facility locations and vehicle routing decision. The system includes fixed cost of self-vehicle and variable transportation costs, the fixed costs of distribution center construction, and the transportation costs of outsourcing. According to the characteristics of the problem, the hierarchical coding method is designed for genetic algorithm. Through the simulation example, the proposed strategy is compared with the traditional complete self-delivery and outsourcing operation mode. The results show that the proposed strategy could effectively reduce the additional cost of self-delivery and the construction cost of the distribution center, thus reducing the system cost. Our proposed is experimentally proved to reduce the system cost by 8.08% and 25.03% compared to the complete self-delivery and outsourcing operation mode, respectively. Finally, the impact of different outsourcing price on the systematic decisions is investigated by sensitivity analysis.
目前国内外对于车辆路径问题研究较多,但对定位运输问题关注较少,定位运输线路安排问题是车辆路径问题的拓展。1959年Dantzig和Ramser[
相比现有的企业单一物流模式,通过自营与外包配送策略相结合的网络拓展模式,可以更容易地在较短时间内实现业务的网点覆盖,从而提高企业的市场占有率。鉴于此,本文提出联合外包策略的定位运输问题,通过将一部分配送任务外包给从事配送业务的企业增加货物运输的灵活型并降低系统成本,以期为物流系统整合设计提供参考。
对比于传统的定位运输线路规划网络,假设客户点(需求点)的需求既可以采用完全外包的方式由第三方企业来完成,也可以采用自送和外包联合的形式完成需求量供给,外包车辆可以从配送中心取货后送往各客户点,并且无需返回配送中心(如
图 1自送路径和外包路径的差别
Fig.1 The difference between self-delivery and outsourcing path
对于该联合外包运输的定位运输问题的模型构建中,假设有R处可能利用的服务中心的设施点,用G{r|r=1,⋯,R}来表示服务中心的集合;对于服务的客户点假设网络中有N个,用H{i|i=R+1,⋯,R+N}来表示客户点或称为需求点的位置集合;用S{G}⋃{H}来表示服务中心与客户点的位置集合;在该服务运输网络中假设有k辆车,并用V{vk|k=1,⋯,K}来表示运输工具能通过的路径或是道路。构建的模型中运用到的其它符号及其含义如下:Cij表示从某一点i到另一点j的单位距离运输花费成本;Fr表示当在某一地点r处设立一个设施点所需要的建设成本;qj表示某一需要服务的位置点所需自送运输的平均估计需求量;Qk表示某一运输工具的容量;dij表示从位置点i到另外一个位置点j的运输行走距离;Xrjk,Xrmk表示某一个车辆k从设施点r朝目标服务点j、m出发完成服务,当车辆行驶时是1,没有车辆行驶则为0;F表示当运输由第三方物流公司负责,即采用外包策略时收取的每单位每公里货物的运输价格;Oi表示某一位置点i的货物需求量由外包运输完成的部分;Di表示某一位置点i的全部货物需求量;lni表示某一位置点i距离某一个设施点n的距离;yi表示规划处的运输路径上到达i点的次序;Ck表示使用第k辆车辆所对应的固定成本;ai表示规定的开始服务需求点i的最早时间又称之为时间窗上限;si表示服务车辆到达需要服务的需求点i的时间;bi表示规定的开始服务需求点i的最晚时间又称之为时间窗下限;αi表示车辆提前到达需求点i进行等待的时间惩罚成本;βi表示车辆到达需求点i迟到的时间惩罚成本;tij表示车辆从需求点i到达需求点j的走行时间;fi表示车辆在i点进行服务的时间。
联合外包策略的定位运输问题数学模型中,包含三个决策变量Xk、Xijk、Zr,其赋值情况如下:
Xk={当第k辆车辆被使用时,取值为1 否则,0 |
Xijk={当k车从点i到达另一点j时,取值为1否则,0 |
Zr={当在某点r建设设施点时,取值为1否则,0 |
对于本文构建的联合外包策略的定位运输线路规划问题模型,其物流网络的总成本主要包括自营车辆的固定成本和可变运输成本、配送服务中心建设的固定成本、外包配送的总成本、以及时间窗约束所带来的延误惩罚成本。因此,模型的目标函数表示如下:
f(x)=min[∑i∈S∑j∈S∑k∈VCijXijkdij+∑k∈VCkXk |
+∑r∈GFrZr+∑n∈G∑i∈HFlniOi+Ti(ti)] | (1) |
Ti(ti)=∑i∈Sαimax [(ai-si),0] |
-∑i∈Sβimax [(si-bi),0] | (2) |
s.t.
∑i∈S∑k∈VXijk≤1 ,∀j∈H | (3) |
∑j∈S∑k∈VXijk≤1 ,∀i∈H | (4) |
∑i∈SXipk-∑j∈SXpjk=0 ,∀k∈V,p∈S | (5) |
∑r∈G∑j∈HXrjk≤1,∀k∈V | (6) |
∑j∈S∑i∈HqjXijk≤Qk,∀k∈V | (7) |
qi+ Oi=Di,∀i∈H | (8) |
∑k∈kXrmk+Zr+Zm≤2 ,∀m∈G,r∈G | (9) |
M·∑j∈G∑k∈VXijk≥qi ,∀i=R+1,⋯,R+N | (10) |
∑k∈V∑j∈HXrjk-Zr≥0 ,∀r∈G | (11) |
∑j∈HXrjk-Zr≤0,∀k∈V,r∈G | (12) |
yi-yj+(R+N)·Xijk≤R+N-1, | (13) |
∀R+1≤i≠j≤R+N,k∈V |
si+fi+tij-M(1-Xijk)≤sj, | (14) |
∀i,j∈S,k∈V |
Xijk=0,1 ,∀i,j∈S,k∈V | (15) |
Zr=0,1 ,∀r∈G | (16) |
Xk=0,1 ,∀k∈V | (17) |
对于这类NP难题的求解,遗传算法[
针对联合外包的定位运输问题,采用实数编码进行染色体的编写,当有N个需求点、以及最多K辆货车时染色体分段编码设计如
该染色体的设计一共分为四段,一共有N+N+N+K个基因位。第一段的N个基因位用来表示每个客户点使用的车辆,每个客户点均有一个对应的基因位,这个基因位上数字表示相应的客户点使用的车辆编号。第二段的N个基因位表示对应的各客户点的服务顺序,通过对基因位上的自然数排序,得到对应客户点的服务顺序。第三段的基因位表示相应客户点的自送需求量。最后的第四段染色体,每个基因位上的数字表示对应车辆的出发和返回的设施点。
下面通过举例来说明该染色体的编码和解码方式,假设有一物流网络使用四辆车即K=4,有三个客户点即N=3,和两个设施点即R=2。某一染色体如
图2 某一染色体构成范例
Fig. 2 Example of a chromosome composition
利用表
具体配送路径,第二段染色体提供了每个需求点的服务顺序,于是得出最终的自送的配送路径为配1→2→1→配1。最后利用染色体的第三段可以得到自送量和外包量。
通过对于染色体的编码设计完成对于车辆数量、服务次序、单独车辆服务对应需求点、自送量与外包量的和为总需求量等的约束限制,针对无法利用编码设计实现的限制,如对于车辆配送路径的最长限制和车辆的最高运输量的限制,通过设置惩罚函数的形式来实现。
适应值代表了对应染色体的存活概率的大小,本文可利用目标函数的值来表示对应染色体的适应值。适应函数的值充分考虑约束限制,利用惩罚函数来实现。如果某一种群中有n条染色体,则种群中的每条染色体的适应值用Fi(i∈n)来表示。
2.4.1 染色体选择设计
染色的选择利用每条染色体对应的适应度采用轮盘赌选择方法进行选择,适应度越高的染色体被选中的概率越大。且将每一父代中的最优染色体加入子代中,进一步提高子代优良性。染色体被选中的概率为pi=Fi∑ni=1Fi(i∈n) ,此外产生的0至1随机数为randi(i∈n)。如果pi<randi(randi∈[0,1],i∈n),则第i条染色体被选中。
2.4.2 染色体交叉设计
利用双点交叉法来进行染色体的交叉,选取两条父代的染色体,在父代染色体上随机抽取两个基因位,随后将这两个基因位之间的染色体进行交叉互换。染色体交叉的概率需提前选定好。如果选出染色体的某一片段编码为C1(1 1 1 4),另一条的相应片段编码为C2(2 3 1 1),选出的两个基因位用下划线表示,交叉之后染色体编码为C1’(1 3 1 1),C2’(2 1 1 4)。
2.4.3 染色体变异设计
根据提前设置好的变异率,对于选出的染色体上两个抽取的基因位之间的变异段进行变异的操作,从而丰富染色体的多样性,避免求解的早熟和局部优化现象。上述例子中的C1( 1 1 1 4 )变异之后为C1”( 1 4 3 2 )。
将某市某区的配送网络中各个成本的关系抽象为一个简单的联合外包配送网络,其中有14个等待服务的需求点,目前有4个可能新建的设施点(作为运载中心)。在满足每个需求点的需求量基础上,可以通过建设设施点进行自送,或者依靠外包策略进行外送。为了更好的刻画该运输网络中的内在关系并利于价格敏感性分析的开展,定义40 km为一个单位长度,即车辆行驶速度为1 单位长度/h。每部车辆的综合固定成本为10 元/天,自送的成本为1 元/40 km;由于该配送网络较小,每个点的距离比较近,外包运输服务提供商的外包成本价格为0.5 元/kg(非跨区小范围运输不考虑运输的距离,仅仅考虑运输量),自送车辆的最大运输距离为40 km,最大运输量为300 kg,一个设施点的建设成本以每日成本进行简单折算后为30 元。
编号 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
坐标 | (18.7 15.29) | (12.21 14.5) | (20.07 10.14) | (19.39 13.37) | (25.27 14.24) | (22 10.04) |
需求量 | 40 | 30 | 25 | 55 | 30 | 15 |
编号 | 7 | 8 | 9 | 10 | 11 | 12 |
坐标 | (25.47 17.02) | (15.79 15.1) | (14.17 9.76) | (14.05 18.12) | (11.25 11.04) | (24 19.89) |
需求量 | 40 | 25 | 30 | 20 | 25 | 35 |
编号 | 13 | 14 | 15配 | 16配 | 17配 | 18配 |
坐标 | (19.41 18.13) | (22.11 12.51) | (17.53 17.38) | (16.6 12.38) | (23.52 13.45) | (16.47 8.45) |
需求量 | 30 | 50 | 0 | 0 | 0 | 0 |
编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
时间窗上限 | 8:00 | 5:00 | 4:06 | 1:30 | 6:00 | 6:30 | 13:54 |
时间窗下限 | 11:00 | 10:30 | 12:54 | 10:54 | 19:36 | 10:48 | 19:48 |
服务时间 | 0:12 | 0:48 | 0:24 | 0:06 | 0:42 | 0:18 | 0:12 |
编号 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
时间窗上限 | 10:06 | 15:30 | 2:30 | 10:12 | 13:00 | 2:18 | 15:12 |
时间窗下限 | 12:00 | 3:06 | 19:54 | 15:36 | 20:18 | 6:30 | 00:00 |
服务时间 | 0:12 | 0:18 | 0:18 | 0:06 | 0:30 | 0:30 | 0:36 |
设置染色体长度为50个基因位,初始基因种群为80个,进行500次迭代,多次求解得出最优的可行解。如
图 3 联合外包策略的定位运输网络图
Fig. 3 Transport network map about location routing problem based on outsourcing strategy
编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
自送量 | 38 | 30 | 25 | 55 | 29 | 15 | 40 |
外包量 | 2 | 0 | 0 | 0 | 1 | 0 | 0 |
自送到达时刻 | 8:00 | 5:00 | 4:00 | 10:14 | 12:03 | 6:25 | 15:32 |
编号 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
自送量 | 24 | 30 | 20 | 0 | 35 | 0 | 48 |
外包量 | 1 | 0 | 0 | 25 | 0 | 30 | 2 |
自送到达时刻 | 13:38 | 16:41 | 9:51 | - | 18:58 | - | 20:40 |
该联合外包策略下的可行解对应自送车辆的运输路径为车辆1:18-3-6-5-7-12-18,车辆2:18-2-10-8-14-18,车辆3:18-1-4-9-18。该可行解使用的配送中心个数为1,对应配送中心为18;使用的车辆数为3;总的成本为168.67元(包括自送成本、外包成本、固定成本、时间惩罚成本等)。
其它10次求解的结果如
针对该运输网络,如果采用完全自送的方式,在其他的基础数据和时间窗限制不变的情况下,利用遗传算法进行求解。并将联合外包运输策略、全部自送和全部外包的配送总成本整理如下
最后,通过敏感性分析考察车辆的综合固定成本、自送的成本、设施点的建设成本以及外包成本的定价对模型系统性能的影响。在相应的成本和定价减少80%、60%、55%、50%、25%和增加25%、50%、100%、150%、200%时,计算自送、外包运输量以及成本的变化,如表
车辆固定成本变动率/% | -80 | -60 | -55 | -50 | -25 | 0 | +25 | +50 | +100 | +150 | +200 |
---|---|---|---|---|---|---|---|---|---|---|---|
总自送量 | 320 | 343 | 374 | 385 | 317 | 389 | 365 | 378 | 281 | 283 | 262 |
总外包量 | 130 | 107 | 76 | 65 | 133 | 61 | 85 | 72 | 169 | 167 | 188 |
运输价格/元 | 162.07 | 163.10 | 168.08 | 165.88 | 172.171 | 168.67 | 181.94 | 181.03 | 202.16 | 216.22 | 222.22 |
设施点建设成本变动率/% | -80 | -60 | -55 | -50 | -25 | 0 | +25 | +50 | +100 | +150 | +200 |
---|---|---|---|---|---|---|---|---|---|---|---|
总自送量 | 329 | 299 | 346 | 265 | 287 | 389 | 296 | 401 | 398 | 309 | 431 |
总外包量 | 121 | 151 | 104 | 185 | 163 | 61 | 154 | 49 | 52 | 141 | 19 |
运输价格/元 | 154.27 | 159.03 | 161.42 | 167.72 | 166.71 | 168.67 | 185.28 | 188.90 | 204.98 | 237.23 | 242.02 |
车辆自送成本变动率/% | -80 | -60 | -55 | -50 | -25 | 0 | +25 | +50 | +100 | +150 | +200 |
---|---|---|---|---|---|---|---|---|---|---|---|
总自送量 | 436 | 380 | 414 | 396 | 371 | 389 | 275 | 254 | 234 | 120 | 120 |
总外包量 | 14 | 70 | 36 | 54 | 79 | 61 | 175 | 196 | 216 | 330 | 330 |
运输价格/元 | 106.49 | 124.63 | 127.36 | 142.77 | 170.01 | 168.67 | 187.95 | 204.03 | 220.50 | 233.24 | 238.89 |
外包价格变动率/% | -80 | -60 | -55 | -50 | -25 | 0 | +25 | +50 | +100 | +150 | +200 |
---|---|---|---|---|---|---|---|---|---|---|---|
总自送量 | 0 | 0 | 0 | 0 | 244 | 389 | 404 | 399 | 415 | 423 | 421 |
总外包量 | 450 | 450 | 450 | 450 | 206 | 61 | 46 | 51 | 35 | 27 | 29 |
运输价格/元 | 45 | 90 | 101.25 | 112.5 | 160.94 | 168.67 | 190.9 | 182.09 | 216.81 | 200 | 206.05 |
从表
考虑实际运营中存在的外包配送业务对定位运输的影响,设计了基于遗传算法的分段编码映射配送中心选址、以及自送和外包运输车辆路径联合决策求解方法。并通过算例验证了联合外包策略的模式相对于完全自送和完全外包模型具有一定的经济优势,能够减少整个运输网络的成本,并结合敏感性分析揭示了外包策略与定位运输之间的相互作用。后续可开展的研究包括:1)考虑配送中心库存对物流系统规划的影响,将问题拓展为库存定位运输问题;2)结合当前绿色新能源车辆的发展趋势,将问题拓展为电动车与柴油车混合模式下的定位运输问题。
DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91. [百度学术]
YU V F, LIN S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers & Operations Research, 2014, 62(2):184-196. [百度学术]
MARINAKIS Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands[J]. Applied Soft Computing, 2015, 37(C):680-701. [百度学术]
RUI B L, FERREIRA C, SANTOS B S. A simple and effective evolutionary algorithm for the capacitated location–routing problem[J]. Computers & Operations Research, 2016, 70(C):155-162. [百度学术]
RIQUELME-RODRÍGUEZ J, GAMACHE M, LANGEVIN A. Location arc routing problem with inventory constraints[J]. Computers & Operations Research, 2016, 76:84-94. [百度学术]
YAKICI E. Solving location and routing problem for UAVs[J]. Computers & Industrial Engineering, 2016, 102:294-301. [百度学术]
MOSHREF-JAVADI M, LEE S. The latency location-routing problem[J]. European Journal of Operational Research, 2016, 255(2):604-619. [百度学术]
SCHIFFER M, WALTHER G. The electric location routing problem with time windows and partial recharging[J]. European Journal of Operational Research, 2017, 260(3):995-1013. [百度学术]
GUO K, ZHANG Q S. A discrete artificial bee colony algorithm for the reverse logistics location and routing problem[J]. International Journal of Information Technology & Decision Making, 2017, 16(2):1-19. [百度学术]
ZHANG D, DONG R, SI Y W, et al. A hybrid swarm algorithm based on ABC and AIS for 2L-HFCVRP[J]. Applied Soft Computing, 2018, 64:468-479. [百度学术]
付旭辉,康玲.遗传算法的早熟问题探究[J].华中科技大学学报(自然科学版),2003,7:53-54. [百度学术]
FU X H, KANG L. Study of the premature convergence of genetic algorithms[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition),2003,7:53-54. [百度学术]
张潜,高立群,胡祥培. 集成化物流中的定位运输路线安排问题(LRP)优化算法评述[J]. 东北大学学报,2003,1:31-34. [百度学术]
ZHANG Q, GAO L Q, HU X P. Review on optimal algorithms of location-routing problem (LRP) in integrated Logistics[J]. Journal of Northeastern University (natural science), 2003,1:31-34. [百度学术]
张潜,高立群,刘雪梅,等. 定位-运输路线安排问题的两阶段启发式算法[J]. 控制与决策,2004,7:773-777. [百度学术]
ZHANG Q, GAO L Q, LIU X M, et al. A two-phase heuristic approach to the location routing problem [J]. Control and Decision, 2004,7:773-777. [百度学术]
王正国,王红卫,刘会新.双目标时变速度车辆路径问题的模型及算法[J].华中科技大学学报(自然科学版),2005,34(12):88-91. [百度学术]
WANG Z G, WANG H W, LIU H X. Mode for bi-objective time dependent vehicle routing problem and its algorithm[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition),2005,34(12):88-91. [百度学术]
王绍仁,马祖军. 震害紧急响应阶段应急物流系统中的LRP[J]. 系统工程理论与实践,2011(8):1497-1507. [百度学术]
WANG S R, MA Z J. Location-routing problem in emergency logistics system for post-earthquake emergency relief response [J]. Systems Engineering-Theory & Practice, 2011(8):1497-1507. [百度学术]
王永,胥冬川,农兰晶.震后过渡阶段应急物流系统的定位-运输路线安排问题研究[J].计算机应用,2015,35(1):243-246. [百度学术]
WANG Y, XU D C, NONG L J. Research of location-routing problem in emergency logistics system for post-earthquake transitional stage[J]. Journal of Computer Applications,2015,35(1):243-246. [百度学术]
王占中,赵利英,曹宁博.基于多层编码遗传算法的危险品运输调度模型[J].吉林大学学报(工学版),2017,47(3):751-755. [百度学术]
WAND Z Z, ZHAO L Y, CAO N B. Hazardous material transportation scheduling model based on mutilayer coding genetic algorithm[J]. Journal of Jilin University (engineering and technology edition), 2017, 47(3):751-755. [百度学术]
李珍萍,周文峰,张煜炜,等.考虑卸载顺序约束的成品油二次配送车辆路径问题研究[J/OL].控制与决策,2019-05-08 [2019-07-07]. https://doi.org/ 10.13195/j.kzyjc.2 018 .1756. [百度学术]
LI Z P, ZHOU W F, ZHANG Y W, et al. Research on vehicle routing problem of refined oil secondary distribution considering unloading sequence constraints [J/OL]. Control and Decision,2019-05-08 [2019-07-07].https://doi.org/10.13195/j. kzyjc.2018.1756. [百度学术]
45
浏览量
104
下载量
2
CSCD
相关文章
相关作者
相关机构