[1]李嫚嫚,陆建,安颖.考虑客户偏好的双目标时间窗指派车辆路径问题[J].东南大学学报(自然科学版),2018,48(3):568-575.[doi:10.3969/j.issn.1001-0505.2018.03.028]
 Li Manman,Lu Jian,An Ying.Bi-objective time window assignment vehicle routing problem considering customer preferences for time windows[J].Journal of Southeast University (Natural Science Edition),2018,48(3):568-575.[doi:10.3969/j.issn.1001-0505.2018.03.028]
点击复制

考虑客户偏好的双目标时间窗指派车辆路径问题()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
48
期数:
2018年第3期
页码:
568-575
栏目:
交通运输工程
出版日期:
2018-05-20

文章信息/Info

Title:
Bi-objective time window assignment vehicle routing problem considering customer preferences for time windows
作者:
李嫚嫚陆建安颖
东南大学城市智能交通江苏省重点实验室, 南京210096; 东南大学现代城市交通技术江苏高校协同创新中心, 南京210096; 东南大学交通学院, 南京210096
Author(s):
Li Manman Lu Jian An Ying
Jiangsu Key Laboratory of Urban ITS, Southeast University, Nanjing 210096, China
Jiangsu Province Collaborative Innovation Center of Modern Urban Traffic Technologies, Southeast University, Nanjing 210096, China
School of Transportation, Southeast University, Nanjing 210096, China
关键词:
交通工程 车辆路径问题 时间窗指派 多目标遗传算法 不确定需求
Keywords:
traffic engineering vehicle routing problem time window assignment multi-objective genetic algorithms uncertain demand
分类号:
U492.3
DOI:
10.3969/j.issn.1001-0505.2018.03.028
摘要:
基于现实中客户对服务时间窗有特定偏好,将最大化客户满意度作为优化目标,对双目标时间窗指派车辆路径问题展开研究.在该问题中,供应商需为每一客户许诺一个服务时间窗.在许诺服务时间窗时,服务期间客户每天需求量尚未确定.在构建了混合整数线性规划模型的基础上,采用不同约束处理依据帕累托方法设计了2个多目标遗传算法:抛弃法约束处理多目标遗传算法和无参约束处理多目标遗传算法.经数值试验测试表明,2个多目标遗传算法都能获得有效的非支配解集,抛弃法约束处理多目标遗传算法的求解质量显著地优于无参约束处理多目标遗传算法.另外,客户满意度与期望配送成本之间存在着制约关系,客户满意度从最小到最大的提升率高于期望配送成本的提升率.
Abstract:
A biobjective time window assignment vehicle routing problem(BOTWAVRP)considering customers’ preferences for time windows was introduced. The two objectives were used to maximize the satisfaction levels of total customers and minimize the expected delivery cost. In this problem, a time window per customer has to be assigned before everyday demand is known within a period. A mix-integer linear programming model for BOTWAVRP was constructed and two multi-objective genetic algorithms(MOGAs)using different constraint handling methods were designed, called the MOGA with rejection and MOGA without penalty-parameter. Computational results show both of two MOGAs can obtain effective non-dominated sets considering the two objectives and the non-dominated set obtained by MOGA with rejection outperforms that of MOGA without penalty-parameter. It exists the restrictive relationship between two objectives. And the improvement ratio of satisfactory levels of the total customers from the minimal value to the maximal value is higher than that of the expected delivery cost.

参考文献/References:

[1] Spliet R, Desaulniers G. The discrete time window assignment vehicle routing problem [J]. European Journal of Operational Research, 2015, 244(2): 379-391. DOI:10.1016/j.ejor.2015.01.020.
[2] Spliet R, Gabor A F. The time window assignment vehicle routing problem [J]. Transportation Science,2015, 49(4): 721-731. DOI:10.1287/trsc.2013.0510.
[3] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints [J]. Operations Research, 1987, 35(2): 254-265. DOI:10.1287/opre.35.2.254.
[4] Lau H C, Sim M, Teo K M. Vehicle routing problem with time windows and a limited number of vehicles [J]. European Journal of Operational Research,2003, 148(3): 559-569. DOI:10.1016/S0377-2217(02)00363-6.
[5] Hashimoto H, Yagiura M, Ibaraki T. An iterated local search algorithm for the time dependent vehicle routing problem with time windows [J]. Discrete Optimization, 2008, 5(2): 434–456. DOI: 10.1016/j.disopt.2007.05.004.
[6] Baldacci R, Mingozzi A, Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints [J]. European Journal of Operational Research, 2012, 218(1): 1-6. DOI: 10.1016/j.ejor.2011.07.037.
[7] 柴获, 何瑞春, 马昌喜,等. 求解带硬时间窗车辆路径问题的改进UMDA算法 [J]. 交通运输系统工程与信息, 2016, 16(2): 176-182. DOI: 10.16097/j.cnki.1009-6744.2016.02.027.
Chai Hou, He Ruichun, Ma Changxi, et al. A univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time window [J]. Journal of Transportation System Engineering and Information Technology,2016, 16(2):176-182. DOI:10.16097/j.cnki.1009-6744.2016.02.027. (in Chinese)
[8] Agatz N, Campbell A, Savelsbergh M. Time slot management in attended home delivery [J]. Transportation Science, 2011, 45(3): 435-449. DOI:10.1287/trsc.1100.0346.
[9] Campbell A M, Savelsbergh M. Decision support for consumer direct grocery initiatives [J]. Transportation Science, 2005, 39(3): 313-327. DOI:10.1287/trsc.1040.0105.
[10] Ehmke J F, Campbell A M. Customer acceptance mechanisms for home deliveries in metropolitan areas [J]. European Journal of Operational Research, 2014, 233(1): 193-207. DOI:10.1016/j.ejor.2013.08.028.
[11] Jozefowieza N, Semetb F, Talbia E G. Multi-objective vehicle routing problems [J]. European Journal of Operational Research, 2008, 189(2): 293-309. DOI:10.1016/j.ejor.2007.05.055.
[12] Huang Y, Zhao L, Woensel T V, et al. Time-dependent vehicle routing problem with path flexibility [J]. Transportation Research Part B: Methodological, 2017, 95: 169-195. DOI:10.1016/j.trb.2016.10.013.
[13] Pillac V, Gendreau M, Guéret C, et al. A review of dynamic vehicle routing problems [J]. European Journal of Operational Research, 2013, 225(1): 1-11. DOI:10.1016/j.ejor.2012.08.015.
[14] Jung S, Haghani A. Genetic algorithm for the time-dependent vehicle routing problem [J]. Transportation Research Record, 2001, 1771: 164-171. DOI:10.3141/1771-21.
[15] Pierre D M, Zakaria N. Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows [J]. Applied Soft Computing, 2017, 52: 863-876. DOI:10.1016/j.asoc.2016.09.039.
[16] Bean J C. Geneticalgorithms and random keys for sequencing and optimization [J]. ORSA Journal on Computing, 1994, 6(2): 154-160. DOI:10.1287/ijoc.6.2.154.
[17] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI:10.1109/4235.996017.
[18] Zitzler E, Thiele L. Multi-objective evolutionary algorithms: A comparative case study and the strength pareto approach [J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271. DOI:10.1109/4235.797969.

相似文献/References:

[1]周竹萍,任刚,王炜.基于方式分担需求的城市道路等级配置模型[J].东南大学学报(自然科学版),2009,39(5):1075.[doi:10.3969/j.issn.1001-0505.2009.05.041]
 Zhou Zhuping,Ren Gang,Wang Wei.Road network gradation optimization model according to traffic demand[J].Journal of Southeast University (Natural Science Edition),2009,39(3):1075.[doi:10.3969/j.issn.1001-0505.2009.05.041]
[2]卓曦,钱振东,张宁.大型公共建筑同向机动车出入口间距计算[J].东南大学学报(自然科学版),2012,42(3):560.[doi:10.3969/j.issn.1001-0505.2012.03.033]
 Zhuo Xi,Qian Zhendong,Zhang Ning.Spacing calculation for same-side vehicle access of large public building[J].Journal of Southeast University (Natural Science Edition),2012,42(3):560.[doi:10.3969/j.issn.1001-0505.2012.03.033]
[3]肖忠斌,王炜,李文权,等.城市高架路下匝道地面联接段最小长度模型[J].东南大学学报(自然科学版),2007,37(6):1071.[doi:10.3969/j.issn.1001-0505.2007.06.026]
 Xiao Zhongbin,Wang Wei,Li Wenquan,et al.Minimum-length-requirement model for expressway off-ramp joint[J].Journal of Southeast University (Natural Science Edition),2007,37(3):1071.[doi:10.3969/j.issn.1001-0505.2007.06.026]
[4]葛宏伟,王炜,陈学武,等.公交站点车辆停靠对信号交叉口进口道交通延误模型[J].东南大学学报(自然科学版),2006,36(6):1018.[doi:10.3969/j.issn.1001-0505.2006.06.029]
 Ge Hongwei,Wang Wei,Chen Xuewu,et al.Traffic delay at signal-controlled intersection with bus stop upstream[J].Journal of Southeast University (Natural Science Edition),2006,36(3):1018.[doi:10.3969/j.issn.1001-0505.2006.06.029]
[5]许项东,程琳,邱松林.交通分配自适应梯度投影算法的敏感性分析[J].东南大学学报(自然科学版),2013,43(1):226.[doi:10.3969/j.issn.1001-0505.2013.01.041]
 Xu Xiangdong,Cheng Lin,Qiu Songlin.Sensitivity analysis of self-adaptive gradient projection traffic assignment algorithm[J].Journal of Southeast University (Natural Science Edition),2013,43(3):226.[doi:10.3969/j.issn.1001-0505.2013.01.041]
[6]郭延永,刘攀,吴瑶,等.基于属性识别的高速公路交通安全设施系统评价[J].东南大学学报(自然科学版),2013,43(6):1305.[doi:10.3969/j.issn.1001-0505.2013.06.032]
 Guo Yanyong,Liu Pan,Wu Yao,et al.Evaluation of freeway traffic safety facility system based on attribute recognition[J].Journal of Southeast University (Natural Science Edition),2013,43(3):1305.[doi:10.3969/j.issn.1001-0505.2013.06.032]
[7]姜军,陆建,李娅.基于驾驶人视认特性的城市道路指路标志设置[J].东南大学学报(自然科学版),2010,40(5):1089.[doi:10.3969/j.issn.1001-0505.2010.05.039]
 Jiang Jun,Lu Jian,Li Ya.Setting of road guide signs based on driver’s recognition characteristics[J].Journal of Southeast University (Natural Science Edition),2010,40(3):1089.[doi:10.3969/j.issn.1001-0505.2010.05.039]
[8]沈家军,王炜,陈学武.城市道路交叉口混合交通流机动车与非机动车冲突概率[J].东南大学学报(自然科学版),2010,40(5):1093.[doi:10.3969/j.issn.1001-0505.2010.05.040]
 Shen Jiajun,Wang Wei,Chen Xuewu.Study on conflict probability of motor and non-motor mixed traffic at urban intersections[J].Journal of Southeast University (Natural Science Edition),2010,40(3):1093.[doi:10.3969/j.issn.1001-0505.2010.05.040]
[9]王炜,陈淑燕,胡晓健.“一路一线直行式”公交模式下公交车行驶诱导和调度集成方法[J].东南大学学报(自然科学版),2008,38(6):1110.[doi:10.3969/j.issn.1001-0505.2008.06.033]
 Wang Wei,Chen Shuyan,Hu Xiaojian.Novel integrated method of bus speed guidance and dispatching based on “one route one line and run straight mode”[J].Journal of Southeast University (Natural Science Edition),2008,38(3):1110.[doi:10.3969/j.issn.1001-0505.2008.06.033]
[10]李志斌,王炜,赵德,等.机非物理分隔道路上自行车超车事件模型[J].东南大学学报(自然科学版),2012,42(1):156.[doi:10.3969/j.issn.1001-0505.2012.01.029]
 Li Zhibin,Wang Wei,Zhao De,et al.Modeling bicycle passing events on physically separated roadways[J].Journal of Southeast University (Natural Science Edition),2012,42(3):156.[doi:10.3969/j.issn.1001-0505.2012.01.029]

备注/Memo

备注/Memo:
收稿日期: 2017-10-10.
作者简介: 李嫚嫚(1991—),女,博士生;陆建(联系人),男,博士,教授,博士生导师,lujian_1972@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(51478110)、江苏省自然科学基金资助项目(BY2016076-05).
引用本文: 李嫚嫚,陆建,安颖.考虑客户偏好的双目标时间窗指派车辆路径问题[J].东南大学学报(自然科学版),2018,48(3):568-575. DOI:10.3969/j.issn.1001-0505.2018.03.028.
更新日期/Last Update: 2018-05-20