Study On Vehicle Routing Problem With Complicated Non-Ergodic Characteristics

As the third profit source for the enterprises to reduce resource consumption and to raise labor productivity, modern logistics is characterized more and more intensively by improved organization mode and advanced management techniques.Among them the Vehicle Routing Problems (VRP) and its extensions have long being interested both industrial and academic people. Good solutions to VRP are always not easy to obtain.Current studies on VRP rely heavily on the basic hypothesis that the routing is "ergodic", i.e., vehicle will pass all the nodes (cities). Unfortunately, this is not practically true for most problems. In most cases, the only known is a map containing geographical distributions of cities and the routing task itself: demand of freight, time limit, penalty on overdue, etc. Traditional algorithms are not suitable for solving this class of VRP with complicated non-ergodic characteristics and complicated but practical restrictions.This thesis details the investigation, development and implementation of efficient algorithms and techniques for optimization of VRP. The main focus is on borrowing ideas from the functions, characteristics, phenomena of living systems, and developing heuristic approach for the solving.Main contributions are briefed as follows:1) Vehicle Routing Problem with complicated non-ergodic characteristics was presented, which was illustrated by analysis of business mode and scheduling demand of the railroad transportation subsidiary company of a largepetrochemical corporation. This type of optimization problem extends the research of VRP.2) Traditional algorithms for solving VRP were reviewed and their difficulties were outlined. Capturing ideas from philosophy of modular programming, a new structural method with good generality and expandability was presented.3) A new simulated evolutionary algorithm, Smart Ant Colony Algorithm (SACA), was developed based on Ant Colony Algorithm (ACA). With food attraction and ants' self-determination introduced and simulated, our ants showed certain degree of intelligence. Numerical experiments demonstrated validity and high efficiency of SACA in solving a complicated and non-ergodic vehicle routing task.