基于顾客时间满意度的车辆路径问题

doi:10.12066/j.issn.1007-2861.2042

上海大学学报(自然科学版) ›› 2020, Vol. 26 ›› Issue (3): 472-480.doi: 10.12066/j.issn.1007-2861.2042

基于顾客时间满意度的车辆路径问题

李常敏(), 陶颖, 彭显, 姚连杰

上海大学管理学院, 上海 200444

收稿日期:2017-12-21 出版日期:2020-06-30 发布日期:2020-01-09
通讯作者: 李常敏 E-mail:lcm@shu.edu.cn
基金资助:
国家自然科学基金资助项目(71401097);上海市教委基金资助项目(13YJC630072)

Vehicle routing problem from the perspective of customer time satisfaction

LI Changmin(), TAO Ying, PENG Xian, YAO Lianjie

School of Management, Shanghai University, Shanghai 200444, China

Received:2017-12-21 Online:2020-06-30 Published:2020-01-09
Contact: LI Changmin E-mail:lcm@shu.edu.cn

摘要/Abstract

摘要：

考虑到普通带时间窗约束的车辆路径问题 (vehicle routing problem with time windows, VRPTW) 模型不能真正反映顾客对时间的偏好, 故在车辆路径优化模型的基础上, 结合顾客时间满意度函数, 同时放松需求点经过即被服务的约束限制, 允许多次经过同一需求点的情况发生, 而需求点只能被同一辆车服务一次, 建立了基于顾客时间满意度的车辆配送 (vehicle routing problem with satisfaction, VRPWS) 模型, 并利用模拟退火算法编程求解. 为验证 VRPWS 模型的有效性进行了数值实验. 实验结果表明: 与传统的带软时间窗约束的车辆路径优化 (vehicle routing problems with soft time window, VRPSTW) 模型和 VRPTW 相比, VRPWS 模型配送效益提升了 170.0% 和 3.2%. 分析结果表明该工作在一定程度上有助于物流企业在配送过程中提高顾客满意度和降低运输成本.

关键词: 顾客时间满意度, 配送路径优化, 车辆配送模型

Abstract:

Considering the fact that the common vehicle routing problem model with time window (VRPTW) constraint cannot truly reflect customers' preferences of time, a modified vehicle routing optimization model based on customer time satisfaction function (vehicle routing problem with satisfaction (VRPWS) model) has been proposed. This new model is designed by relaxing the restriction that each demand point should be served if passed so as to allow vehicles to pass all demand points many times. And the simulate anneal algorithm is used to solve this problem. In order to illustrate the validity of VRPWS, a numerical example has been introduced. Through the numerical simulation and calculation, it is found that the VRPWS model is superior to the traditional vehicle routing optimization model with soft time window (VRPSTW) constraints and the vehicle routing optimization model with time window constraints in that it increases the delivery revenue by 170.0% and 3.2% respectively. This study helps logistics enterprises to improve their customer satisfaction and reduce their transportation costs in the delivery process.

Key words: customer time satisfaction, distribution path optimization, VRPWS

中图分类号:

O221

李常敏, 陶颖, 彭显, 姚连杰. 基于顾客时间满意度的车辆路径问题[J]. 上海大学学报(自然科学版), 2020, 26(3): 472-480.

LI Changmin, TAO Ying, PENG Xian, YAO Lianjie. Vehicle routing problem from the perspective of customer time satisfaction[J]. Journal of Shanghai University（Natural Science Edition）, 2020, 26(3): 472-480.

图/表 5

参考文献 16

[1]	Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959,6(1):80-91.
[2]	Balakrishnan N. Simple heuristics for the vehicle routing problem with soft time windows[J]. Journal of the Operational Research Society, 1993,44(3):279-287.
[3]	武佳佳, 段会川. 软时间窗支持的医药物流公司配送路径优化研究[J]. 山东师范大学学报(自然科学版), 2017,32(1):54-60.
[4]	Manisri T, Mungwattana A, Janssens G K, et al. A hybrid algorithm for the vehicle routing problem with soft time windows and hierarchical objectives[J]. Journal of Information and Optimization Sciences, 2015,36(3):283-300.
[5]	Beheshti A, Hejazi S. A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window[J]. Information Sciences, 2015,316(21):598-615.
[6]	Tas D Jabali O van Woensel T. A vehicle routing problem with flexible time windows[J]. Computers and Operations Research, 2014,52:39-54. doi: 10.1016/j.cor.2014.07.005
[7]	Tas D, de Llaert N, van Woensel T, et al. The time-dependent vehicle routing problem with soft time windows and stochastic travel times[J]. Transportation Research Part C: Emerging Technologies, 2014,48:66-83. doi: 10.1016/j.trc.2014.08.007
[8]	李进, 张江华. 基于碳排放与速度优化的带时间窗车辆路径问题[J]. 系统工程理论与实践, 2014,34(12):3063-3072.
[9]	李珍萍, 赵菲, 刘洪伟. 多时间窗车辆路径问题的智能水滴算法[J]. 运筹与管理, 2015,24(6):1-10.
[10]	穆东, 王超, 王胜春, 等. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015,21(6):1626-1636.
[11]	李想, 李苏剑, 李宏. 两级选址-路径问题的大规模邻域搜索模拟退火算法[J]. 工程科学学报, 2017,39(6):953-961.
[12]	李江伟, 许伦辉. 退火算法与神经网络算法结合在路径规划中的研究 [J]. 自动化与仪表, 2017, 32(11):6-9; 31.
[13]	任力. 基于时间满意度的建设项目选址模型及应用[J]. 统计与决策, 2015(14):39-42.
[14]	齐艳, 王飞, 贾晋. 基于顾客时间满意度的生鲜农产品配送中心选址研究[J]. 物流技术, 2014,33(7):215-218.
[15]	韩瑜睿. 基于满意度函数的公共自行车租赁服务点选址问题研究[D]. 兰州: 兰州交通大学, 2016.
[16]	Li G, Bie Z, Xie H, et al. Customer satisfaction based reliability evaluation of active distribution networks[J]. Applied Energy, 2016,162:1571-1578.

基于顾客时间满意度的车辆路径问题

Vehicle routing problem from the perspective of customer time satisfaction

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 16

相关文章 1

编辑推荐

Metrics

本文评价