考虑时间窗服务价值的越库车辆路径优化

beoplay体育提现学报（社会科学版） ›› 2019, Vol. 29 ›› Issue (2): 12-12.

考虑时间窗服务价值的越库车辆路径优化

刘虹,林楚玥

福州大学经济与管理学院,福建福州 350100

收稿日期:2018-11-14 出版日期:2019-06-25 发布日期:2019-09-05
作者简介:刘虹（1973-）,女,福建三明人,福州大学经济与管理学院副教授,研究方向：物流与供应链管理、智能算法|林楚玥（1993-）,女,福建厦门人,福州大学经济与管理学院管理科学与工程硕士研究生,研究方向：物流与供应链管理
基金资助:
福建省自然科学基金项目“智慧物流配送网络动态集成与自适应优化模型及其算法”(2014J05082)

Optimization for Vehicle Routing Problem with Cross-docking considering the Value of Time Window Service

LIU HONG,LIN CHUYUE

School of Economic and Management, Fuzhou University, Fuzhou, 350100,China

Received:2018-11-14 Online:2019-06-25 Published:2019-09-05

摘要/Abstract

摘要：

越库配送网络具有低存储、高效率等特性,其实施的关键在于内部的协同到库、分拣和外部的车辆配送路径的有效融合。与此同时,配送环境的复杂性增加配送时间的不确定性,使物流服务接受者感知到不同的服务价值差异。本文结合前景理论,构造客户时间窗服务价值函数,并建立寻求时间窗服务价值最大和总成本最小的越库物流配送多目标优化模型。根据优化模型的特征,设计了禁忌搜索算法和局部搜索算法相结合的混合算法,通过算例仿真,验证了优化模型和求解算法是可行和有效的。

关键词: 越库配送, 车辆路径, 前景理论, 多目标优化, 禁忌搜索算法

Abstract:

The cross-docking distribution network has the characteristics of low storage and high efficiency, and the key to its implementation is the effective integration of internal coordination, sorting and external vehicle routing. Meanwhile, the complexity of the distribution environment increases the uncertainty of delivery time, making logistics service recipients perceive different service value. Combined with the prospect theory, the customer time window service value function is given. And a multi-objective optimization model for cross-docking logistics distribution aimed to find the lowest total cost and the largest value of time window service is proposed. Then, a hybrid algorithm combining tabu search algorithm and local search algorithm is designed to find the optimal solution. Finally, the simulation of the example verify the feasibility and effectiveness of the model and the algorithm.

Key words: cross-docking, vehicle routing, prospect theory, multi-objectives, tabu search algorithm

中图分类号:

F252.1

刘虹,林楚玥. 考虑时间窗服务价值的越库车辆路径优化[J]. beoplay体育提现学报（社会科学版）, 2019, 29(2): 12-12.

LIU HONG,LIN CHUYUE. Optimization for Vehicle Routing Problem with Cross-docking considering the Value of Time Window Service[J]. Journal of Xidian University(Social Sciences Edition), 2019, 29(2): 12-12.

图/表 7

图1

图2

表1

表2

表3

表4

图3

参考文献 16

[1]	BELLE J V, VALCKENAERS P, CATTRYSSE D . Cross-docking:state of the art[J]. Omega, 2012,40(6):827-846.
[2]	LEE Y H, JUNG J W, LEE K M . Vehicle routing scheduling for cross-docking in the supply chain[J]. Computers & Industrial Engineering, 2006,51(2):247-256.
[3]	LIAO C J, LIN Y, SHIH S C . Vehicle routing with cross-docking in the supply chain[J]. Expert Systems with Applications, 2010,37(10):6868-6873.
[4]	WEN M, LARSEN J, CLAUSEN J , et al. Vehicle routing with cross-docking[J]. Journal of the Operational Research Society, 2009,60(12):1708-1718.
[5]	YU V F, JEWPANYA P REDI A A N P ,. Open vehicle routing problem with cross-docking[J]. Computers & Industrial Engineering, 2016,94(C):6-17.
[6]	曹克官 . 越库环境下基于调度策略的设施选址问题研究[D]. 上海:上海交通大学, 2009: 9-55.
[7]	葛显龙, 邹登波 . 供应链环境下带越库配送的车辆路径问题[J]. 计算机工程与应用, 2018,54(24):252-259.
[8]	BANIAMERIAN A, BASHIRI M, TAVAKKOLI-MOGHADDAM R . Modified variable neighborhood search and genetic algorithm for profitable heterogeneous vehicle routing problem with cross-docking[J]. Applied Soft Computing Journa, 2019,75:441-460.
[9]	MAKNOON Y, LAPORTE G . Vehicle routing with cross-dock selection[J]. Computers & Operations Research, 2017,77:254-266.
[10]	FAN J . The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction[J]. Procedia Engineering, 2011,15:5284-5289.
[11]	CHEN D, CAO E, LAI W . A differential evolution algorithm for pickups and deliveries problem with fuzzy time windows[J]. Journal of Intelligent & Fuzzy Systems, 2016,30(1):267-277.
[12]	楼振凯 . 带模糊时间窗的配送问题多目标优化研究[J].模糊系统与数学, 2017(3):187-194.
[13]	王君 . 模糊时间窗VRP的动态规划和禁忌搜索混合算法[J]. 计算机工程与应用, 2014,50(24):58-64.
[14]	任亮, 黄敏, 王兴伟 . 考虑客户拖期厌恶行为的4PL路径优化问题[J]. 计算机集成制造系统, 2016,22(4):1148-1154.
[15]	董宗然, 周慧 . 禁忌搜索算法评述[J].软件工程, 2010(z1):96-98.
[16]	KAHNEMAN D, TVERSKY A . Prospect theory:an analysis of decision making under risk[J]. ECONOMETRICA, 1979,47(2):263-291.

	小规模	大规模
取、送货节点总数	10	50
可用车辆数	10	30
最晚工作时间	1440	1440
车辆最大载量	70	150
每台车辆固定成本	50	50
各节点间的运输成本	U(20,200)	U(20,200)
各节点间的运输时间	U(48,560)	U(48,560)
订单货物量	U(5,50)	U(5,30)
供应商数量	4	12
零售商数量	5	38
订单数	24	150
客户期望送货时间点	U(330,450)	U(620,740)
客户可容忍送货时间点	U(510,630)	U(800,920)

路径序号	行车时间	装货时间	路径	调度顺序
路径序号	行车时间	装货时间	总时间	调度顺序
1	186.3	19	205.3	3
2	205	20.5	225.5	1
3	187.8	21.5	209.3	2
4	148.4	21.5	169.9	4

方案	总成本	时间窗服务价值	配送路线
1	1985.96	0.7900	$(O,{{D}_{1}},{{D}_{2}},O)$ $(O,{{D}_{5}},{{D}_{6}},O)$ $(O,{{D}_{3}},{{D}_{4}},O)$
2	1989.75	0.8019	$(O,{{D}_{6}},{{D}_{3}},O)$ $(O,{{D}_{1}},{{D}_{5}},O)$ $(O,{{D}_{2}},{{D}_{4}},O)$

超过可容忍时间服务价值为负（场景1）			超过可容忍时间服务价值为零（场景2）
方案	总成本	时间窗服务价值	方案	总成本	时间窗服务价值
1	7305.6307	0.7277	1	7196.0434	0.7766
2	7312.4614	0.7332	2	7226.6867	0.7963
3	7326.4932	0.7555	3	7252.0494	0.8086
4	7338.4690	0.7676	4	7287.4849	0.8088
5	7341.1607	0.7739	5	7288.5132	0.8139
6	7366.7729	0.7857	6	7303.1282	0.8235
7	7411.1896	0.7901	7	7345.5161	0.8266
8	7449.1274	0.7938	8	7363.9384	0.8306
9	7474.2663	0.7955	9	7384.5629	0.8314
10	7553.7202	0.8075	10	7469.0772	0.8558
11	7646.2436	0.8084	11	7481.1030	0.8583
12	7742.0140	0.8230	12	7506.1456	0.8609
13	7749.7318	0.8234	13	7522.0388	0.8618
			14	7530.2345	0.8634
			15	7598.1125	0.8644
			16	7670.1785	0.8647