工业工程

工业工程 ›› 2019, Vol. 22 ›› Issue (6): 67-73.doi: 10.3969/j.issn.1007-7375.2019.06.009

• 专题论述 • 上一篇    下一篇

带装载能力的需求依背包拆分车辆路径问题

芦娟1, 夏扬坤2, 邹安全3, 符卓4, 王松5, 魏占国2, 符瑛2   

  1. 1. 湖南工程职业技术学院 管理工程系, 湖南 长沙 410151;
    2. 中南林业科技大学 物流与交通学院, 湖南 长沙 410004;
    3. 佛山科学技术学院 经济管理与法学院, 广东 佛山 528000;
    4. 中南大学 交通运输工程学院, 湖南 长沙 410075;
    5. 湖南商学院 工商管理学院, 湖南 长沙 410205
  • 收稿日期:2019-02-21 发布日期:2019-12-24
  • 通讯作者: 夏扬坤(1989-),男,湖南省人,讲师,博士,主要研究方向为物流系统优化,E-mail:jiaochyk166@163.com E-mail:jiaochyk166@163.com
  • 作者简介:芦娟(1981-),女,湖南省人,讲师,硕士,主要研究方向为物流配送、物流系统优化
  • 基金资助:
    国家社会科学基金资助项目（17BJY008）；湖南省社科基金资助项目（17YBA430）；湖南省教育厅科学研究资助项目（18C1317）；湖南省教育厅优秀青年基金项目（19B610）；中南林业科技大学引进人才科研启动基金项目（2019YJ005）

A Capacitated Vehicle Routing Problem with Split Deliveries by Backpack

LU Juan1, XIA Yangkun2, ZOU Anquan3, FU Zhuo4, WANG Song5, WEI Zhanguo2, FU Ying2   

  1. 1. Management Engineering Department, Hunan Vocational College of Engineering, Changsha 410151, China;
    2. School of Logistics and Transportation, Central South University of Forestry and Technology, Changsha 410004, China;
    3. School of Business and Law, Foshan University, Foshan 528000, China;
    4. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China;
    5. College of Business Administration, Hunan University of Commerce, Changsha 410205, China
  • Received:2019-02-21 Published:2019-12-24

RichHTML

14

PDF

5766

摘要： 以最小化总的旅行时间为优化目标，以单车场、单车型、装载能力和需求依背包拆分等为约束条件，将以往客户需求不可拆分的条件松弛为依背包来离散拆分，建立了带装载能力的需求依背包拆分VRP（CVRPSDB）的单目标数学模型。设计了一个自适应禁忌搜索算法（ATSA）对模型进行求解。该算法采用了自适应惩罚机制，构建了一个多邻域结构体，并针对客户点与背包都设计了相应的邻域操作算子，较好地适应了客户需求量的离散拆分程度。经算例测试与文献对比，验证了所设计模型与算法的有效性。

关键词: 车辆路径问题, 拆分, 依背包拆分, 禁忌搜索算法, 物流

Abstract: Taking the shortest total travel time as the optimization object, a model of single objective programming is constructed, which contains a series of constraints, such as single depot, single vehicle type, loading capacity limitation, split deliveries by backpack and so on. An adaptive tabu search algorithm (ATSA) is designed to solve the problem. The ATSA uses a series of optimization strategies to improve the search ability, such as an adaptive penalty mechanism and a multi-neighborhood structure, and designs corresponding neighborhood operators for both customer points and backpack, which can better adapt to the discrete splitting degree of customer demands. The validity of the proposed model and algorithm is demonstrated by the comparison of the test results with the literature.

Key words: vehicle routing problem, split, split deliveries by backpack, tabu search algorithm, logistics

中图分类号: