带回程取货的逆向物流车辆路径建模及其蚁群算法

交通运输系统工程与信息 ›› 2010, Vol. 10 ›› Issue (3): 110-114 .

带回程取货的逆向物流车辆路径建模及其蚁群算法

胡天军^*1;程文科²

1.北京交通大学交通运输学院，北京 100044； 2.中粮屯河股份有限公司，乌鲁木齐 830000

收稿日期:2010-02-14 修回日期:2010-04-11 出版日期:2010-06-25 发布日期:2010-06-25
通讯作者: 胡天军
作者简介:胡天军(1963-)，女，北京人，副教授

Modeling of Vehicle Routing Problems with Backhauls of Reverse Logistics and Ant Colony Algorithm

HU Tian-jun¹;CHENG Wen-ke²

1.School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China; 2.COFCO TUNHE CO.LTD., Urumqi 830000, China

Received:2010-02-14 Revised:2010-04-11 Online:2010-06-25 Published:2010-06-25
Contact: HU Tian-jun

摘要/Abstract

摘要： 对逆向物流车辆路径问题进行了概述和分类，构建了以VRPPDTW为基础的带回程取货的逆向物流车辆路径数学模型，设计了求解该模型的最大—最小蚁群算法，对设计要素进行了详细介绍，包括初始蚁群分布，状态转移策略，以及信息素更新策略等，并给出了具体的算法步骤. 最后，以Solomon中的R101、R102、R103、R104和R105等5项示例为背景，分别取前25节点和50节点，以取货点的取货量比例分别占全部客户节点需求量的10％、30％、50％取货，得到30个算例的计算结果，并将其与Tangian和模拟退火等计算结果进行了比较，结果表明最大—最小蚁群算法在某种程度上优于其他算法

关键词: 城市交通, 逆向物流, 车辆路径, 时间窗, 蚁群算法

Abstract: This paper summarized the vehicle routing problem with reverse logistics and its classification. A mathematical model of the vehicle problem with reverse logistics was constructed based on VRPPDTW and a max-min ant colony algorithm was designed to solve this model. Then, the elements such as initial ant distribution, strategy of state-transition, and pheromone update strategy were introduced and specific calculate steps of the algorithm were provided. In the example, the anterior 25 nodes and 50 nodes are selected under the background of five examples of R101, R102, R103, R104, and R105 in Solomon. The proportions of the waste from every nodes were 10％, 20％, and 30％, respectively, and the results of 30 examples were obtained. They were also compared with the results from Tangian and simulated annealing algorithm. It was found that the max-min ant colony algorithm was superior to other algorithms to some extent.

Key words: urban traffic, reverse logistic, vehicle route, time windows, ant colony algorithm

中图分类号:

U491

胡天军,程文科. 带回程取货的逆向物流车辆路径建模及其蚁群算法[J]. 交通运输系统工程与信息, 2010, 10(3): 110-114 .

HU Tian-jun,CHENG Wen-ke. Modeling of Vehicle Routing Problems with Backhauls of Reverse Logistics and Ant Colony Algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 10(3): 110-114 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17987.shtml

http://www.tseit.org.cn/CN/Y2010/V10/I3/110

参考文献

［1］郭伏, 隆颖. 带时窗回程取货的车辆路径问题的算法［J］. 东北大学学报（自然科学版）,2006,27(5):575-578.［GUO F, LONG Y. On the algorithm for VRPBTW (vehicle routing problem with backhauls and time windows)［J］. Journal of Northeastern University (Natural Science), 2006,27(5):575-578.］

［2］郎茂祥. 配送车辆优化调度模型与算法［M］. 北京：电子工业出版社,2009,3:2-7. ［LANG M X. The model and algorithm for distribution vehicle scheduling problem［M］. Beijing: Publishing House of Electronics Industry, 2009,3:2-7.］

［3］佟璐,聂磊,赵鹏. 蚁群算法在动车组运用问题中的应用［J］. 交通运输系统工程与信息,2009,9(6): 161-167.［TONG L, NIE L, ZHAO P. Application of ant colony algorithm in train-set scheduling problem［J］. Transportation Systems Engineering and Information, 2009:9(6):161-167.］

［4］陶胤强,牛惠民. 带时间窗的多车型多费用车辆路径问题的模型和算法［J］. 交通运输系统工程与信息,2008,8(1): 113-117.［TAO Y Q, NIU H M. Model and heuristic algorithm for the multi-type vehicles routing problem with multiple costs and time windows limits［J］. Journal of Transportation Systems Engineering and Information Technology,2008,8(1):113-117.］

［5］Anne W, Said S. An ant system algorithm for the vehicle routing problem with backhauls［C］. 4th Metaheuristics International Conference, 2001: 199-203.

［6］李士勇. 蚁群算法及其应用［M］. 黑龙江: 哈尔滨工业大学出版社, 2004: 35-38.［LI S Y. Ant colony algorithm and its application［M］. Heilongjiang: Harbin Institute of Technology Press, 2004: 35-38.］

［7］Stutzle T, Hoos H. Improvements on the ant system: introducing MAX-MIN ant system［C］// Proceedings of the International Conference on Artificial Neural N

［8］Thomas Stuztle. MAX-MIN ant system［J］. Elsevier Science, Nov, 1999.

［9］Solomon M. Algorithm for the vehicle routing and scheduling problem with time window constraint［J］. Operations Research, 1987, 35: 254-265.

［10］Thangiah S, Potvin J, Sun T. Heuristic approaches to vehicle routing with backhaulsand time windows［J］. Computers Operational Research, 1996, 23(11): 1043-1057.〖JP〗

［11］吴泰熙, 陈正芳, 徐俊诚. 含取货之车辆途程问题解法之研究［J］. Journal of the Chinese Institute of Industrial Engineers, 2003, 20(6): 651-665.［WU T X, CHEN Z F, XU J C. Solving vehicle routing problem with backhauls［J］. Journal of the Chinese Institute of Industrial Engineers, 2003, 20(6): 651-665.］

[1]	刘晓冰, 李奉孝, 田欣妹, 闫学东. 基于通勤模式的都市圈中心结构判别研究[J]. 交通运输系统工程与信息, 2022, 22(2): 17-28.
[2]	许奇, 陈越, 黄靖茹, 高顺祥, 张志健. 考虑出行费用的就业可达性分析[J]. 交通运输系统工程与信息, 2022, 22(2): 37-44.
[3]	刘春禹, 刘永红, 罗霞, 朱颖. 混合交通流环境下单交叉口自动驾驶车辆轨迹优化[J]. 交通运输系统工程与信息, 2022, 22(2): 154-162.
[4]	王宁, 张佳蕊, 赵姣. 城际零担货运平台车辆路径问题研究[J]. 交通运输系统工程与信息, 2022, 22(2): 163-177.
[5]	张小雨, 邵春福, 王博彬, 黄士琛. 新冠疫情影响下居民共享出行方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(2): 186-196.
[6]	李欣, 戴章, 李怀悦, 胡笳. 基于连续近似模型的轨道交通与常规公交耦合优化设计[J]. 交通运输系统工程与信息, 2022, 22(2): 206-213.
[7]	郝妍熙, 刘戎阳, 胡华, 方勇, 刘志钢. 单向通道行人-自行车混合流建模及自组织现象研究[J]. 交通运输系统工程与信息, 2022, 22(2): 223-229.
[8]	赵传林, 贺少松, 孙淑敏, 王钰涵. 基于理性疏忽理论的交通疏散网络双层优化模型[J]. 交通运输系统工程与信息, 2022, 22(2): 239-246.
[9]	陈小红, 蓝秋雨. 不确定交通需求下交叉口信号配时区间优化模型[J]. 交通运输系统工程与信息, 2022, 22(2): 247-256.
[10]	李冰, 王正辉, 马铭炜, 杨鸿宇, 冯悦. 信号交叉口行人二次过街下右转车通行能力与延误估计模型[J]. 交通运输系统工程与信息, 2022, 22(2): 257-267.
[11]	朱彤, 秦丹, 董傲然, 杜雨萌, 魏雯. 公交驾驶员违规类型同交通事故间的关联分析[J]. 交通运输系统工程与信息, 2022, 22(2): 322-329.
[12]	毛保华, 王敏, 何天健, 陈海波. 城市公共交通服务水平研究回顾和展望[J]. 交通运输系统工程与信息, 2022, 22(1): 2-13.
[13]	王子甲, 贾慧慧, 朱亚迪, 陈峰. 基于智能卡数据的轨道与公交复合网络通勤方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(1): 67-73.
[14]	贾斌, 朱凌, 李树凯, 刘家林. 城市轨道交通小交路计划与客流控制协同优化策略[J]. 交通运输系统工程与信息, 2022, 22(1): 124-132.
[15]	牟振华, 汪寒冰, 林本江, 陈逸群, 金程程, 陈艳艳. 基于演化博弈的违章停车动态罚金策略效用仿真评价[J]. 交通运输系统工程与信息, 2022, 22(1): 152-162.