东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2013, Vol. 34 ›› Issue (2): 182-185.DOI: -

• 信息与控制 • 上一篇    下一篇

带时间窗的4PL路径优化问题的两阶段求解

黄敏1，薄桂华1，谢大叶2   

  1. (1东北大学流程工业综合自动化国家重点实验室，辽宁沈阳110819;2沈阳飞机工业(集团)有限公司，辽宁沈阳110850)
  • 收稿日期:2012-05-30 修回日期:2012-05-30 出版日期:2013-02-15 发布日期:2013-04-04
  • 通讯作者: 黄敏
  • 作者简介:黄敏(1968-)，女，福建长乐人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(71071028，70931001，71021061，61070162)；高等学校博士学科点专项科研基金资助项目(20110042110024，20100042110025)；中央高校基本科研业务费专项资金资助项目(N090504006，N100604021，N110204003).

TwoPhase Algorithm for Routing Optimization of FourthParty Logistics with Time Windows

HUANG Min1， BO Guihua1， XIE Daye2   

  1. 1.State Key Laboratory of Synthetical Automation for Process Industries， Northeastern University， Shenyang 110819， China; 2.Shenyang Aircraft Industries
  • Received:2012-05-30 Revised:2012-05-30 Online:2013-02-15 Published:2013-04-04
  • Contact: BO Guihua
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

1091

摘要： 以第四方物流(fourthpartylogistics，4PL)为背景，针对带有时间窗约束的4PL路径优化问题，设计了一个两阶段算法.该算法首先根据和声搜索算法的优化机制在配送网络多重图上产生一个简单图，然后采用删除算法求出简单图上的前K条费用最短路径.该算法能确保产生的解是合法的连通路径，不需要对非法路径进行修复，能保留解的信息且节省大量的计算时间.对不同规模的3个算例进行求解，并与传统的和声搜索算法和枚举算法进行对比分析.结果表明，本文算法的求解效果优于传统的和声搜索算法和枚举算法，是求解该类问题的有效算法.

关键词: 第四方物流, 路径优化, 和声搜索, 两阶段算法, 时间窗

Abstract: Based on the background of fourthparty logistics， a twophase algorithm was proposed for solving the fourthparty logistics routing problem with time windows. A simple graph was generated from a multigraph in the distribution network using harmony search mechanism， and then the top K shortest paths in the simple graph were obtained using deletion algorithm. The proposed algorithm can ensure all the solutions to be feasible paths and the information of solution to be reserved. Because no ineffective paths were needed to be repaired， a lot of computational time can be saved. Three cases of different sizes were solved by the proposed algorithm， and the results were compared with the harmony search and the enumeration algorithms， which shows that the proposed algorithm outperforms the other two ones.

Key words: fourthparty logistics, routing optimization, harmony search, twophase algorithm, time window

中图分类号: