带模糊预约时间的动态VRP的插入启发式算法

张建勇; 李军; 郭耀煌

带模糊预约时间的动态VRP的插入启发式算法

基金项目:

国家自然科学基金资助项目(70071028)

北大联泰供应链系统研究与发展中心资助项目

详细信息

作者简介:
张建勇(1975- ),男,副教授,博士,研究方向为物流系统分析,电话:022-23516141,E-mail:zhangjy94@nankai.edu.cn

计量
- 文章访问数: 1549
- HTML全文浏览量: 63
- PDF下载量: 484
- 被引次数: 0
出版历程
- 收稿日期: 2006-06-18
- 刊出日期: 2008-02-25

Insertion Heuristic Algorithm for Dynamic Vehicle Routing Problem with Fuzzy Due-Time

摘要

摘要: 为有效解决动态环境下考虑顾客偏好的车辆路径优化问题,在对反映顾客偏好的模糊预约时间以及具有模糊预约时间的动态车辆路径问题进行简单描述的基础上,给出了该问题的求解思路,即当新顾客出现时,在保证车辆运载能力和服务时间的可行性的前提下,由最佳车辆在最合适的时间为该新顾客服务.基于此思路,设计了由前后双向可推的推-碰过程确定最佳服务时间的插入启发式算法.在该算法中,通过对顾客的服务时间的前推或后推,确定能使所有顾客的综合满意度达到最大的服务时间调整方案.同时,通过综合考虑顾客满意度、车辆行驶距离和车辆等待时间等因素,使由于新顾客的加入而引起的综合成本增加值得以优化.最后,给出了一个算例,以说明该插入启发式算法求解考虑顾客偏好的动态车辆路径问题的有效性.
- 模糊预约时间 /
- 动态车辆路径问题 /
- 启发式算法
Abstract: In order to effectively solve the dynamic vehicle routing problem with considering the preferences of customers,the traditional static vehicle routing problem with time windows(VRPTW) was expanded to a new situation with dynamic customers,and the time windows were replaced by fuzzy due-time representing the preferences of customers.After a simple description of the fuzzy due-time and the dynamic vehicle routing problem with fuzzy due-time,an insertion heuristic algorithm was proposed.In this algorithm,a two-directional push-bump procedure is employed to decide the optimal time to serve customers,and the average satisfaction degree of customers and the traveling distance and waiting time of vehicles are considered synthetically to optimize the increase of total cost caused by new customers.Finally,an example was presented to show the validity of the proposed algorithm.
- fuzzy due-time /
- dynamic vehicle routing problem /
- heuristic algorithm

HTML全文

参考文献(1)

CHIANG W C,RUSSELL R A.Simulated annealing metaheuristics for the vehicle routing problem with time windows[J].Annals of Operations Research,1996,63 (1):3-27.[2] CHIANG W C,RUSSELL R A.A reactive tabu search metaheuristic for the vehicle routing problem with time windows[J].Informs Journal on Computing,1997,9(4):417-430.[3] POTVIN J Y,ROUSSEAU J M.An exchange heuristic for routing problems with time windows[J].Journal of the Operational Research Society,1995,46(12):1 433-1 446.[4] SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research,1987,35 (2):254-265.[5] BADEAU P,GENDREAU.A parallel tabu search heuristic for the vehicle routing problem with time windows[J].Transportation Research-C,1997,31(1):109-122.[6] POTVIN J Y,KERVAHUT T.The vehicle routing problem with time windows -part Ⅰ:tabu search[J].Informs Journal on Computing,1996,8(2):158-164.[7] POTVIN J Y,BENGIO S.The vehicle routing problem with time windows -part Ⅱ:genetic search[J].Informs Journal on Computing,1996,8(2):165-172.[8] 袁庆达,杜文,周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究[J].西南交通大学学报,2001,36(4):401-406.YUAN Qingda,DU Wen,ZHOU Zailing.Model and algorithms for mixed fleet vehicle routing problem with soft time windows[J].Journal of Southwest Jiaotong University,2001,36(4):401-406.[9] 郭耀煌,李军.车辆优化调度[M].成都:成都科技大学出版社,1994:44-60.[10] CHEN R,GEN M.Vehicle routing problem with fuzzy due-time using genetic algorithms[J].Japanese Journal of Fuzzy Theory and Systems,1995,7(5):1 050-1 061.[11] 张建勇,李军,郭耀煌.具有模糊预约时间的VRP的混合遗传算法[J].管理科学学报,2005,8(3):64-71.ZHANG Jianyong,LI Jun,GUO Yaohuang.Hybrid genetic algorithm to vehicle routing problem with fuzzy due-time[J].Journal of Management Sciences in China,2005,8(3):64-71.[12] BODIN L,GOLDEN B,ASSAD A,et al.Routing and scheduling of vehicles and crews:the state of the art[J].Computer and Operation Research,1983,10(1):62-212.[13] 张建勇,李军.具有模糊旅行时间的VRP的一种混合遗传算法[J].管理工程学报,2006,20(4):13-16.ZHANG Jianyong,LI Jun.A hybrid genetic algorithm to the vehicle routing problem with fuzzy traveling time[J].Journal of Industrial Engineering and Engineering Management,2006,20(4):13-16.[14] 玄光南,程润伟.遗传算法与工程设计[M].北京:科学出版社,2000:244-256.[15] TEODOROVIC D.Fuzzy set theory applications in traffic and transportation[J].European Journal of Operational Research,1994,74(3):379-390.

施引文献

附加材料(0)

访问统计

点击查看大图

计量

文章访问数: 1549
HTML全文浏览量: 63
PDF下载量: 484
被引次数: 0

带模糊预约时间的动态VRP的插入启发式算法

作者简介: 张建勇(1975- ),男,副教授,博士,研究方向为物流系统分析,电话:022-23516141,E-mail:zhangjy94@nankai.edu.cn

计量

出版历程

Insertion Heuristic Algorithm for Dynamic Vehicle Routing Problem with Fuzzy Due-Time

计量

出版历程

目录

作者简介:
张建勇(1975- ),男,副教授,博士,研究方向为物流系统分析,电话:022-23516141,E-mail:zhangjy94@nankai.edu.cn