Volume 14 Issue 3
. 
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2014  >  14(3): 105-110
LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, LU Chao. Multi-agent evolutionary algorithm of VRP problem with time window[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 105-110.
Citation: LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, LU Chao. Multi-agent evolutionary algorithm of VRP problem with time window[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 105-110.
shu

Multi-agent evolutionary algorithm of VRP problem with time window

  • School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

More Information
  • Author Bio:

    LIU Xin-meng (1990-), female, graduate student, +86-10-81687135, 13120872@bjtu.edu.cn

    HE Shi-wei (1969-), male, professor, +86-10-81687135, shwhe@bjtu.edu.cn

  • Received Date: 2014-01-17
  • Publish Date: 2014-06-25
    Abstract
  • Based on the angle of practicality and rationality, the vehicle routing problem with time window for single distribution center was studied.The shortest driving time and the minimum customer waiting time were taken as objective functions, the service time window and vehicle load were taken as constraint conditions, and the bi-objective optimization model was constructed. The Multi-agent evolutionary algorithm based on number coding (NC-MAEA) was used to solve the model, and the calculation result was compared with the calculation result solved by genetic algorithm.Calculation result shows that when the number of customer demand point is 13, the service time of demand point is 5 min, the maximum vehicle load is 3 t, the number of initial agent is 49 and the maximum evolution iterations is 200, the worst value is 121.8 min and the optimal value is 110.3 min calculated by using genetic algorithm after 30 calculation times.The worst value is 113.6 min and the optimal value is 103.6 min calcuated by using the propsed algorithm.It is clear that the higher quality optimal result can be gotten by using the multi-agent evolutionary algorithm, the results change little after repeated tests.

     

    • FullText(HTML)
  • loading
    • References(19)
  • [1]
    CHIEN S, GAO Sheng-yan, MEEGODA J N, et al. Fleet size estimation for spreading operation considering road geometry, weather and traffic[J]. Journal of Traffic and Transportation Engineering: English Edition, 2014, 1 (1): 1-12. doi: 10.1016/S2095-7564(15)30084-2
    [2]
    KALLEHAUGE B. Formulations and exact algorithms for the vehicle routing problem with time windows[J]. Computers and Operations Research, 2008, 35 (7): 2307-2330. doi: 10.1016/j.cor.2006.11.006
    [3]
    RALPHS T K, KOPMAN L, PULLEYBLANK W R, et al. On the capacitated vehicle routing problem[J]. Mathematical Programming, 2003, 94 (2): 343-359.
    [4]
    KOHL N, MADSEN O B G. An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation[J]. Operations Research, 1997, 45 (3): 395-406. doi: 10.1287/opre.45.3.395
    [5]
    JULIEN B, DAVID S. On the effectiveness of set covering formulations for the vehicle routing problem with time windows[J]. Operations Research, 1997, 45 (2): 295-301. doi: 10.1287/opre.45.2.295
    [6]
    吴勇, 叶春明, 马慧民, 等. 基于并行粒子群算法的带时间窗车辆路径问题[J]. 计算机工程与应用, 2007, 43 (14): 223-226. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200714065.htm

    WU Yong, YE Chun-ming, MA Hui-min, et al. Parallel particle swarm optimization algorithm for vehicle routing problems with time windows[J]. Computer Engineering and Applications, 2007, 43 (14): 223-226. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200714065.htm
    [7]
    刘霞, 齐欢. 带时间窗的动态车辆路径问题的局部搜索算法[J]. 交通运输工程学报, 2008, 8 (5): 114-120. http://transport.chd.edu.cn/article/id/200805023

    LIU Xia, QI Huan. Local search alogrithm of dynamic vehicle routing problem with time window[J]. Journal of Traffic and Transportation Engineering, 2008, 8 (5): 114-120. (in Chinese). http://transport.chd.edu.cn/article/id/200805023
    [8]
    刘志硕, 申金生, 柴跃廷. 基于自适应蚁群算法的车辆路径问题研究[J]. 控制与决策, 2005, 20 (5): 562-566. doi: 10.3321/j.issn:1001-0920.2005.05.018

    LIU Zhi-shuo, SHEN Jin-sheng, CHAI Yue-ting. Vehicle routing problem based on an adaptive ant colony algorithm[J]. Control and Decision, 2005, 20 (5): 562-566. (in Chinese). doi: 10.3321/j.issn:1001-0920.2005.05.018
    [9]
    潘立军, 符卓. 求解带硬时间窗车辆路径问题的时差插入启发式算法[J]. 计算机应用, 2012, 32 (11): 3042-3043, 3070. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201211019.htm

    PAN Li-jun, FU Zhuo. Time difference insertion heuristics algorithm for vehicle routing problem with hard time window[J]. Journal of Computer Applications, 2012, 32 (11): 3042-3043, 3070. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201211019.htm
    [10]
    BANOS R, ORTEGA J, GIL C, et al. A simulated annealingbased parallel multi-objective approach to vehicle routing problems with time windows[J]. Expert System with Application, 2013, 40 (5): 1696-1707. doi: 10.1016/j.eswa.2012.09.012
    [11]
    GILLETT B E, MILLER L R. A Heuristic algorithm for the vehicle-dispatch problem[J]. Operations Research, 1974, 22 (3): 340-349.
    [12]
    GLOVER F. Tabu search—part Ⅰ[J]. QRSA Journal on Computing, 1989, 1 (3): 190-206.
    [13]
    周屹, 李海龙, 王锐. 遗传算法求解物流配送中带时间窗的VRP问题[J]. 吉林大学学报: 理学版, 2008, 46 (2): 300-303. https://www.cnki.com.cn/Article/CJFDTOTAL-JLDX200802029.htm

    ZHOU Yi, LI Hai-long, WANG Rui. VRP problem with time windows in the logistics and distribution solved by genetic algorithm[J]. Journal of Jilin University: Science Edition, 2008, 46 (2): 300-303. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JLDX200802029.htm
    [14]
    龚延成, 郭晓汾, 尤晓铃, 等. 基于遗传算法的物流配送车辆调度问题研究[J]. 数学的实践与认识, 2004, 34 (6): 93-97. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htm

    GONG Yan-cheng, GUO Xiao-fen, YOU Xiao-ling, et al. Solving the vehicle routing and scheduling problems by genetic algorithms[J]. Mathematics in Practice and Theory, 2004, 34 (6): 93-97. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htm
    [15]
    郎茂祥, 胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学, 2002, 10 (5): 51-56. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200205010.htm

    LANG Mao-xiang, HU Si-ji. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm[J]. Chinese Journal of Management Science, 2002, 10 (5): 51-56. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200205010.htm
    [16]
    马宇红, 姚婷婷, 张浩庆. 基于分区的多配送中心多车型车辆调度问题与遗传算法设计[J]. 科技导报, 2013, 31 (2): 61-67. https://www.cnki.com.cn/Article/CJFDTOTAL-KJDB201302024.htm

    MA Yu-hong, YAO Ting-ting, ZHANG Hao-qing. Multidelivery centre multi-type vehicle scheduling problem based on the partition and the design of genetic algorithm[J]. Science and Technology Review, 2013, 31 (2): 61-67. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-KJDB201302024.htm
    [17]
    袁志. 解排列优化的整数编码多智能体进化算法[J]. 软件, 2011, 32 (5): 24-26. https://www.cnki.com.cn/Article/CJFDTOTAL-RJZZ201105009.htm

    YUAN Zhi. Number coding multi-agent evolutionary algorithm for deployment optimization[J]. Computer Engineering and Software, 2011, 32 (5): 24-26. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-RJZZ201105009.htm
    [18]
    曾聪文, 古天龙. 求解装配序列规划的一种多智能体进化算法[J]. 计算机集成制造系统, 2009, 15 (9): 1803-1808. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200909020.htm

    ZENG Cong-wen, GU Tian-long. Multi-agent evolutionary algorithm for assembly sequence planning[J]. Computer Integrated Manufacturing Systems, 2009, 15 (9): 1803-1808. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200909020.htm
    [19]
    边霞, 米良. 遗传算法理论及其应用研究进展[J]. 计算机应用研究, 2010, 27 (7): 2425-2429, 2434. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201007006.htm

    BIAN Xia, MI Liang. Developmenton genetic algorithm theory and its applications[J]. Application Research of Computers, 2010, 27 (7): 2425-2429, 2434. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201007006.htm
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (677) PDF downloads(1244) Cited by()
    Proportional views
    Related

    Copyright《Journal of Traffic and Transportation Engineering》编辑部陕ICP备05001904号-1

    Address ：Editorial Department of Journal of Traffic and Transportation Engineering, Chang 'an University, Middle Section of South Second Ring Road, Xi 'an, Shaanxi（710064） Tel：029-82334388 Email：jygc@chd.edu.cn

    All visit:Today's visit:

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return