带时间窗的多行程交换箱甩挂路径优化

交通运输系统工程与信息 ›› 2020, Vol. 20 ›› Issue (1): 166-174.

带时间窗的多行程交换箱甩挂路径优化

彭勇^*，高鹤

重庆交通大学交通运输学院，重庆 400074

收稿日期:2019-09-25 修回日期:2019-11-25 出版日期:2020-02-25 发布日期:2020-03-02
作者简介:彭勇(1973-)，男，重庆人，教授，博士.
基金资助:
教育部人文社会科学研究规划基金/The Ministry of Education of Humanities and Social Science Project(17YJA630079)；重庆市社会科学规划项目/ Chongqing Social Science Planning Project(2019YBGL049)；重庆交通大学研究生教育创新基金项目/ Chongqing Jiaotong University Graduate Education Innovation Fund Project(2019S0121).

Path Optimization of Multi-trip Swap-body Vehicle Routing Problem with Time Window

PENG Yong, GAO He

School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China

Received:2019-09-25 Revised:2019-11-25 Online:2020-02-25 Published:2020-03-02

摘要/Abstract

摘要：

针对市区—近郊的同城物流配送系统，为尽可能降低物流运输成本的同时提高客户满意度，研究带时间窗的具有多行程的交换箱甩挂运输问题. 在配送系统中，配送车辆从配送中心出发将货物运往各个客户点，由于道路条件的限制，客户点分为只允许小型卡车配送的限制点客户和卡车或带交换箱拖车的整车都可为其配送的灵活点客户. 在客户时间窗和多行程的约束条件下，建立以成本最小为优化目标的基于交换箱甩挂的路径优化模型，提出装箱算法与遗传算法混合的启发式求解算法. 算例验证了所提出算法的有效性，为带交换箱的甩挂车进行物流配送提供一定的决策指导和参考意见.

关键词: 交通运输经济, 交换箱甩挂, 多行程, 时间窗, 装箱算法, 遗传算法

Abstract:

Aiming at the urban- suburban logistics distribution system, in order to reduce the logistics transportation cost and improve customer satisfaction as much as possible, the multi-trip Swap-body transportation problem with time window is studied. In this distribution system, the distribution vehicle carries goods to each customer point from the distribution center. Because of the limitation of road conditions, the customer points are divided into the customers who only allow the distribution of small trucks and the flexible point customers who can be distributed by the truck or the whole vehicle with Swap-body trailer. Under the constraint of customer time window and multi-trip, a path optimization model based on switching body is established, which takes the minimum cost as the optimization goal, and a heuristic algorithm based on the mixture of packing algorithm and genetic algorithm is proposed. An example is given to verify the effectiveness of the proposed algorithm, and to provide some decision guidance and reference for the logistics distribution of the trailer with Swap-body.

Key words: transportation economy, Swap-body vehicle routing problem, multi-trip, time window, packing algorithm, genetic algorithm

中图分类号:

U268.6

彭勇，高鹤. 带时间窗的多行程交换箱甩挂路径优化[J]. 交通运输系统工程与信息, 2020, 20(1): 166-174.

PENG Yong, GAO He. Path Optimization of Multi-trip Swap-body Vehicle Routing Problem with Time Window[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(1): 166-174.

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

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

http://www.tseit.org.cn/CN/Y2020/V20/I1/166

参考文献

[1] HUBER S, GEIGER M J. Swap body vehicle routing problem: A heuristic solution approach[C]. Lecture Notes in Computer Science, 2014: 16-30.

[2] BELHAIZA S, HANSEN P, LAPORTE G. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J]. Computers & Operations Research, 2014(52): 269-281.

[3] CARLSSON J G, BEHROOZI M. Worst- case demand distributions in vehicle routing[J]. European Journal of Operational Research, 2017, 256(2): 462-472.

[4] TIRKOLAEE E B, ALINAGHIAN M, HOSSEINABADI A A R, et al. An improved ant colony optimization for the multi-trip capacitated arc routing problem[J]. Computers & Electrical Engineering, 2019, 77: 457- 470.

[5] 张晓楠, 范厚明. 带时间窗偏好的多行程模糊需求车辆路径优化[J]. 计算机集成制造系统, 2018, 24(10): 89- 105. [ZHANG X N, FAN H M. Vehicle routing optimization with time window preference for multi-trip fuzzy demand[J]. Computer Integrated Manufacturing System, 2018, 24(10): 89-105.]

[6] NGUYEN P K, CRAINIC T G, TOULOUSE M. A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows[J]. European Journal of Operational Research, 2013, 231(1): 43-56.

[7] HERNANDEZ F, FEILLET D, GIROUDEAU R, et al. Branch-and-price algorithms for the solution of the multi- trip vehicle routing problem with time windows [J]. European Journal of Operational Research, 2016, 249(2): 551-559.

[8] 边展, 徐奇, 靳志宏. 带时间窗的甩挂运输路径优化问题研究[J]. 交通运输系统工程与信息, 2018, 18(2): 183-193, 207. [BIAN Z, XU Q, JIN Z H. Research on optimization of hanging transportation path with time window[J]. Traffic and Transportation Systems Engineering and Information, 2018, 18(2): 183-193, 207.]

[9] TOFFOLO T A M, CHRISTIAENS J, VAN MALDEREN S, et al. Stochastic local search with learning automaton for the Swap-body vehicle routing problem[J]. Computers & Operations Research, 2018(89): 68-81.

[10] BEAN J C. Genetic algorithms and random keys for sequencing and optimization[J]． ORSA Journal on Computing，1994, 6 (2): 154-160.

[1]	王健, 王慧, 胡晓伟, 李园园. 高峰期考虑乘客议价的网约车定价与平台收益及社会福利优化[J]. 交通运输系统工程与信息, 2022, 22(2): 54-63.
[2]	王景鹏, 祝蕊, 王鹏飞. 需求不确定下的网约车司机最优工资水平研究[J]. 交通运输系统工程与信息, 2022, 22(2): 178-185.
[3]	刘忠波, 王淇娴, 郑红星. 海空协同的远海岛礁战储物资供给优化模型与算法[J]. 交通运输系统工程与信息, 2022, 22(2): 268-279.
[4]	靳志宏, 焉红, 王小寒, 邢磊, 徐奇. 滚装甩挂运输牵引车调度优化及作业模式类比分析[J]. 交通运输系统工程与信息, 2022, 22(1): 142-151.
[5]	薛运强, 郭军, 钟蒙, 安静. 基于不确定理论的常规公交车辆调度优化[J]. 交通运输系统工程与信息, 2021, 21(6): 115-122.
[6]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[7]	徐素秀, 谢冰, 秦威, 程会兵. 电动汽车充电与换电模式定价及投资策略[J]. 交通运输系统工程与信息, 2021, 21(5): 183-189.
[8]	吕彪, 管心怡, 高自强. 地铁网络服务韧性评估与最优恢复策略[J]. 交通运输系统工程与信息, 2021, 21(5): 198-205.
[9]	鲁皓, 卢鑫, 焦柳丹. 收费公路资产证券化定价及发行方法研究[J]. 交通运输系统工程与信息, 2021, 21(4): 40-46.
[10]	王永, 谭克虎, 张娟. 基础设施公私合营模式融资影响因素及空间溢出效应研究[J]. 交通运输系统工程与信息, 2021, 21(4): 47-53.
[11]	楚金华, 李俊鹤, 王春娟, 陈超. 排放控制区下集装箱班轮航线路径规划与航速调度集成决策[J]. 交通运输系统工程与信息, 2021, 21(4): 230-238.
[12]	赵旭，张汇妍，黄瑞. 节点中断与需求不确定下的港口供应链整合[J]. 交通运输系统工程与信息, 2021, 21(3): 34-39.
[13]	徐智勇. 铁路电分相布设及纵断面协同优化研究[J]. 交通运输系统工程与信息, 2021, 21(3): 170-175.
[14]	刘显贵, 王晖年, 洪经纬, 郝雷. 网联环境下信号交叉口车速控制策略及优化[J]. 交通运输系统工程与信息, 2021, 21(2): 82-90.
[15]	汪茜，柏赟，李佳杰，朱巧珍，冯旭杰. 城市轨道交通地下线车站选址与平面线形优化[J]. 交通运输系统工程与信息, 2021, 21(2): 119-125.