主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2013, Vol. 21 ›› Issue (4): 187-192.

• 论文 • 上一篇    

同时集散货物的开放式车辆路径问题研究

张江华1, 李进2, 高敏刚3   

  1. 1. 山东大学管理学院, 山东 济南 250100;
    2. 浙江工商大学信息学院, 浙江 杭州 310018;
    3. 中国科学院科技政策与管理科学研究所, 北京 100190
  • 收稿日期:2012-07-27 修回日期:2013-04-18 出版日期:2013-08-30 发布日期:2013-08-24
  • 基金资助:
    国家自然科学基金资助项目(71201093);山东省优秀中青年科学家科研奖励基金项目(BS2012SF012);教育部人文社科青年项目(12YJC630091);浙江省自然科学基金项目(LQ12G02007);山东大学自主创新基金项目(2012TS194)

Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups

ZHANG Jiang-hua1, LI Jin2, GAO Min-Gang3   

  1. 1. School of Management, Shandong University, Jinan 250100, China;
    2. School of Information, Zhejiang Gongshang University, Hangzhou 310018, China;
    3. Institute of Policy and Management, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2012-07-27 Revised:2013-04-18 Online:2013-08-30 Published:2013-08-24

PDF (PC)

2655

被引次数

7

摘要： 本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。

关键词: 车辆路径问题, 同时集散货物, 模型与算法

Abstract: Open vehicle routing problem of multiple distribution centers with simultaneous deliveries and pickups is studied, in which the number and working time of the vehicles are limited. Based on the minimum number and travel distance of vehicles, a multi-objective model is proposed. A novel mixed algorithm based on lagrangian relaxation technique and tabu search algorithm is given, which obtains the maximum lower bound of the optimal solution and then adopts the strategy of assignment and adjustment for clients to achieve the feasible solution. For the tabu search algorithm, a random neighborhood ordering and perturbation mechanisms based on four neighborhood search methods are employed. Computational results show that this algorithm is effective to search the satisfactory solutions and the open collaborative arrangement of vehicle routing is more economic and reasonable than the close independent arrangement of vehicle routing.

Key words: vehicle routing problem, simultaneous deliveries and pickups, model and algorithm

中图分类号: