求解集送货可拆分车辆路径问题的启发式算法

doi:10.3969/j.issn.1000-565X.2010.03.011

华南理工大学学报（自然科学版） ›› 2010, Vol. 38 ›› Issue (3): 58-63.doi: 10.3969/j.issn.1000-565X.2010.03.011

求解集送货可拆分车辆路径问题的启发式算法

杨亚璪¹靳文舟² 郝小妮² 田晟²

1.华南理工大学工商管理学院, 广东广州 510640; 2.华南理工大学土木与交通学院, 广东广州 510640

收稿日期:2009-07-15 修回日期:2009-10-27 出版日期:2010-03-25 发布日期:2010-03-25
通信作者: 杨亚璪（1981-），男，博士生，主要从事运输物流研究． E-mail:scutyyz@gmail．com
作者简介:杨亚璪（1981-），男，博士生，主要从事运输物流研究．
基金资助:
国家“863”计划资助项目(2007AAI1Z201)；国家自然科学基金资助项目(50878089)

Heuristic Algorithm to Solve Vehicle Routing Problem with Split Pickups and Deliveries

Yang Ya-zao¹Jin Wen-zhou²Hao Xiao-ni²Tian Sheng²

1. School of Business Administration, South China University of Technology, Guangzhou 510640, Guangdong, China; 2. School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, Guangdong, China

Received:2009-07-15 Revised:2009-10-27 Online:2010-03-25 Published:2010-03-25
Contact: 杨亚璪（1981-），男，博士生，主要从事运输物流研究． E-mail:scutyyz@gmail．com
About author:杨亚璪（1981-），男，博士生，主要从事运输物流研究．
Supported by:
国家“863”计划资助项目(2007AAI1Z201)；国家自然科学基金资助项目(50878089)

摘要/Abstract

摘要： 为了节约运输成本、提高物流服务效率，对集送货可拆分的车辆路径问题进行了研究．该问题允许一个任务点被访问多次，也允许同一车辆访问同一任务点多于一次．针对问题的特点设计三阶段启发式算法，拆分部分任务点的集送货需求，并使车辆行驶距离之和最小．数值实验结果表明，新的算法可以得到合理的车辆路径，尤其适用于送货需求总量大于集货需求总量的情形．

关键词: 集送货, 路径优化, 装卸混合, 启发式算法

Abstract:

Heuristic Algorithm to Solve Vehicle Routing Problem with Split Pickups and DeliveriesYang Ya-zao, Jin Wen-zhou, Hao Xiao-ni, Tian Sheng 1. School of Business Administration, South China University of Technology, Guangzhou 510640, Guangdong, China; 2. School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, Guangdong, ChinaAbstract:In order to save the transportation cost and improve the efficiency of logistics services, the vehicle rou- ting problem with split pickups and deliveries is investigated. According to the characteristics of this problem, that is, multiple visits for a certain task point or for the same task point by a certain vehicle are allowed, a three-phase heuristic algorithm, which splits the demands of pickups and deliveries at some task points and minimizes the total driving distance of vehicles, is proposed. Numerical results show that the proposed algorithm helps to obtain reaso- nable vehicle routings, especially with the case of total delivery amount being greater than total pickup amount.

Key words: pickup and delivery, route optimization, handling mixture, heuristic algorithm

杨亚璪靳文舟郝小妮田晟. 求解集送货可拆分车辆路径问题的启发式算法[J]. 华南理工大学学报（自然科学版）, 2010, 38(3): 58-63.

Yang Ya-zao Jin Wen-zhou Hao Xiao-ni Tian Sheng. Heuristic Algorithm to Solve Vehicle Routing Problem with Split Pickups and Deliveries[J]. Journal of South China University of Technology (Natural Science Edition), 2010, 38(3): 58-63.

[1]	李家乐刘真伯王雪菲. 智能电网下支持充放电策略的电动汽车配送路径优化[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 31-40.
[2]	胡宝雨艾雨豪程国柱. 基于地铁线路的常规公交局域网络协调调度模型 [J]. 华南理工大学学报（自然科学版）, 2021, 49(1): 134-141.
[3]	王学武夏泽龙顾幸生. 基于 DMOEA/D-ET 算法的焊接机器人多目标路径规划[J]. 华南理工大学学报（自然科学版）, 2019, 47(4): 99-106.
[4]	焦玉玲徐良成李津张鹏李思本 . 基于有向网络理论的 U 型装配线平衡问题研究 [J]. 华南理工大学学报（自然科学版）, 2018, 46(2): 53-58.
[5]	陈凤超李融林. 基于路由代价的无线传感器网络蚁群路由算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(5): 36-43.
[6]	邹焱飚张铁陈伟华. 孔群钻削机械手的运动规划和加工路径优化[J]. 华南理工大学学报（自然科学版）, 2010, 38(8): 56-60.
[7]	朱明英叶梧冯穗力何晓明. MPLS网络中支持Diffserv流量工程的抢占算法[J]. 华南理工大学学报（自然科学版）, 2008, 36(8): 54-58,74.
[8]	周炳海蒋舒宇何平奚立峰. 基于双重资源的柔性生产系统调度算法[J]. 华南理工大学学报（自然科学版）, 2008, 36(4): 45-49.
[9]	林伟伟齐德昱刘波. 基于资源融合的网格任务调度模型与算法[J]. 华南理工大学学报（自然科学版）, 2008, 36(1): 32-37.
[10]	丁伟. 具有通用机的四组工件排序问题[J]. 华南理工大学学报（自然科学版）, 2005, 33(10): 108-111.

求解集送货可拆分车辆路径问题的启发式算法

Heuristic Algorithm to Solve Vehicle Routing Problem with Split Pickups and Deliveries

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价