Volume 10 Issue 2
. 
Turn off MathJax
Article Contents
Article Navigation >  Journal of Traffic and Transportation Engineering  > 2010  >  10(2): 99-103
QI Wen-xiang, LU Zhi-qiang, SUN Xiao-ming. Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window[J]. Journal of Traffic and Transportation Engineering, 2010, 10(2): 99-103. doi: 10.19818/j.cnki.1671-1637.2010.02.018
Citation: QI Wen-xiang, LU Zhi-qiang, SUN Xiao-ming. Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window[J]. Journal of Traffic and Transportation Engineering, 2010, 10(2): 99-103. doi: 10.19818/j.cnki.1671-1637.2010.02.018
shu

Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window

doi: 10.19818/j.cnki.1671-1637.2010.02.018

  • School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240, China

More Information
  • Author Bio:

    QI Wen-xiang(1984-), male, graduate student, +86-21-34206782, sjtuqwx@gmail.com

    LU Zhi-qiang(1968-), male, associate professor, +86-21-34206782, zhiqianglu@sjtu.edu.cn

  • Received Date: 2009-12-18
  • Publish Date: 2010-04-25
    Abstract
  • Multi-vehicle routing problem with pickups and deliveries was studied, and soft time window constraint was considered by adding time punishment cost. The mathematical model was built, and its optimized object was the minimum of combination with vehicle rent cost, transportation cost and time punishment cost, and the model was solved by using heuristic saving algorithm. Time punishment cost and transpiration cost were calculated respectively, and the relation between direct and indirect deliveries was compared to obtain best routes. Test result indicates that when the times of pickups and deliveries reach 50, the average loading rate of freight car still achieves above 80%, so the heuristic saving algorithm can reduce the distance without loadage and rent times, and optimize total cost.

     

    • FullText(HTML)
  • loading
    • References(11)
  • [1]
    CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12 (4): 568-581. doi: 10.1287/opre.12.4.568
    [2]
    GILLETT B E, MILLER L R. Aheuristic algorithm for the vehicle-dispatch problem[J]. Operations Research, 1974, 22 (2): 340-349. doi: 10.1287/opre.22.2.340
    [3]
    MONTANE F A T, GALVAO R D. A tabu search algorithmfor the vehicle routing problem with si multaneous pickup and delivery service[J]. Computers & Operations Research, 2006, 33 (3): 595-619.
    [4]
    NAGY G, SALHI S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research, 2005, 162 (1): 126-141. doi: 10.1016/j.ejor.2002.11.003
    [5]
    李军. 有时间窗的车辆路线安排问题的启发式算法[J]. 系统工程, 1996, 14 (5): 45-50. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT199605009.htm

    LI Jun. A heuristic algorithmfor vehicle routing scheduling problem with time windows[J]. Systems Engineering, 1996, 14 (5): 45-50. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT199605009.htm
    [6]
    唐勇, 刘峰涛. 新型遗传模拟退火算法求解带VRPTW问题[J]. 计算机工程与应用, 2006, 42 (7): 7-9. doi: 10.3321/j.issn:1002-8331.2006.07.003

    TANG Yong, LIU Feng-tao. New genetic si mulated annealing algorithmfor vehicle routing problem with time window[J]. Computer Engineering and Applications, 2006, 42 (7): 7-9. (in Chinese) doi: 10.3321/j.issn:1002-8331.2006.07.003
    [7]
    霍佳震, 张磊. 有时间窗的集货送货一体化车辆路径规划启发式算法研究[J]. 物流技术, 2004, 23 (5): 64-66. doi: 10.3969/j.issn.1005-152X.2004.05.025

    HUO Jia-zhen, ZHANG Lei. Study on heuristic algorithm for picking-delivery problem with time window constraint[J]. Logistics Technology, 2004, 23 (5): 64-66. (in Chinese) doi: 10.3969/j.issn.1005-152X.2004.05.025
    [8]
    张燕, 周支立, 翟斌. 集货送货一体化的物流配送车辆路线问题的标号算法[J]. 运筹与管理, 2007, 16 (3): 12-19. doi: 10.3969/j.issn.1007-3221.2007.03.003

    ZHANG Yan, ZHOU Zhi-li, ZHAI Bin. Multi-attribute label matching algorithm for vehicle routing problems with time windows and backhauls[J]. Operations Research and Management Science, 2007, 16 (3): 12-19. (in Chinese) doi: 10.3969/j.issn.1007-3221.2007.03.003
    [9]
    屈援, 汪波, 钟石泉. 单车场集送一体化车辆路径问题及其混合算法研究[J]. 武汉理工大学学报: 交通科学与工程版, 2007, 31 (5): 811-814. doi: 10.3963/j.issn.2095-3844.2007.05.015

    QU Yuan, WANG Bo, ZHONG Shi-quan. Research on singledepot integrated vehicle routing problem and its hybrid algorithm[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2007, 31 (5): 811-814. (in Chinese) doi: 10.3963/j.issn.2095-3844.2007.05.015
    [10]
    赵鲁华. 城市多网点配送车辆调度模型与算法研究[J]. 物流技术, 2007, 26 (8): 91-93. doi: 10.3969/j.issn.1005-152X.2007.08.028

    ZHAO Lu-hua. Study on vehicle scheduling model and algorithmfor city multi-node delivery[J]. Logistics Technology, 2007, 26 (8): 91-93. (in Chinese) doi: 10.3969/j.issn.1005-152X.2007.08.028
    [11]
    郎茂祥, 胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学, 2002, 10 (5): 51-56. doi: 10.3321/j.issn:1003-207X.2002.05.011

    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) doi: 10.3321/j.issn:1003-207X.2002.05.011
    • 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 (452) PDF downloads(517) 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