A Multi start Variable Neighborhood Descent Algorithm for Two echelon Vehicle Routing Problem
CSTR:
Author:
Affiliation:

College of Electronics and Information Engineering, Tongji University,College of Electronics and Information Engineering, Tongji University,College of Electronics and Information Engineering, Tongji University,College of Electronics and Information Engineering, Tongji University

Clc Number:

TP273

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Two echelon vehicle routing problem(2E VRP) is a novel kind of vehicle routing problem in which freight from depot to customers is compulsorily delivered through intermediate depots (named satellites). The first echelon is from depot to satellites, while the second from satellites to customers. This paper proposes a multi start variable neighborhood descent algorithm to solve 2E VRP according to the characteristics of this problem. First, an improved Split algorithm continuously splits random permutations of all customers until a feasible second echelon distribution scheme appears. Then, a complete initial feasible solution is obtained by solving the first echelon problem and then further improved by a variable neighborhood descent (VND). When no improvements can be found by VND, the preceding process is repeated by multi start skills until the algorithm is terminated. Computational results show that the proposed algorithm is easy to implement and it outperforms the best two existing heuristics for 2E VRP.

    Reference
    Related
    Cited by
Get Citation

ZENG Zhengyang, XU Weisheng, XU Zhiyu, NI Jiacheng. A Multi start Variable Neighborhood Descent Algorithm for Two echelon Vehicle Routing Problem[J].同济大学学报(自然科学版),2014,42(10):1530~1535

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 16,2013
  • Revised:July 02,2014
  • Adopted:May 12,2014
  • Online: October 14,2014
  • Published:
Article QR Code