Font Size: a A A

A Two-Phase Heuristic Algorithm For The Vehicle Routing Problem And Its Application To Logistic Distribution

Posted on:2005-03-03Degree:DoctorType:Dissertation
Country:ChinaCandidate:X DaiFull Text:PDF
GTID:1116360125467505Subject:Management Science and Engineering
Abstract/Summary:PDF Full Text Request
A key element of logistic distribution systems is the routing of vehicles, which have been asubject of management science. This paper is concerned with the research on vehicle routingproblem in logistic systems, under the research on the heuristic algorithm for the Vehicle RoutingProblem with Time Windows (VRPTW) and the design of interactive solving. Vehicle routing problem involves the design of a set of minimum-cost vehicle routes,delivering the right commodities to the right location by the very method at the very time. Andlogistic distribution requires delivering the right commodities to the right place by the rightmethod at the right time. So vehicle routing problem represents a very important part of anylogistic distribution systems. VRPTW involves the design of a set of minimum-cost vehicle routes, originating andterminating at a central depot, for a fleet of vehicles that services a set of customers with knowndemands. Each customer is serviced exactly once and, furthermore, all the customers must beassigned to vehicles without exceeding vehicle capacities. With the allowable pick-up timewindows at each customer location, no vehicle is allowed to arrive too late at a customer location,and a waiting time is introduced in the route if the vehicle arrives too early. Quite often, a timewindow is also added to the depot, in order to define a scheduling horizon. Belonging to NP-hard problems, VRPTW is usually solved by use of local search heuristicstarting from an initial solution, where the methods include edge exchange, node interchange orrelocation. To avoid local minima and ultimately find the desired solution, Metaheuristics, such asTabu Search, Genetic Algorithm, Ant Colony Optimization, Simulated Annealing and et al, havereceived a lot of attention in the recent years. Firstly, this paper presents a two-phase heuristic for solving VRPTW as follows. 1) Introduces an edge exchange operator. That is, replacing multiple edges within each routeof multiple routes by other multiple edges. Where the number of the related routes and the numberof the replaced edges within each route are upper bounded, and the replaced edges belongs to asubset of the edge set of the current solution.2) Introduces an node relocation operator. That is, relocating multiple nodes within eachroute of multiple routes. Where the number of the related routes and the number of the relocatednodes within each route are upper bounded, and the relocated nodes belongs to a node subset. 3) Illustrates the sweep heuristics for constructing a feasible solution of VRPTW. Wherevirtual vehicle will be introduced if no available vehicle can service the residual nodes. 4) Presents a two-phase heuristic for solving VRPTW based on the above research, and itscomputational study. The results is, the local search algorithm based on the above operatorsevidently improve the initial solution constructed by the sweep algorithm, and the solutions areclose to the best known solutions identified by heuristics. Secondly, this paper design a scheme for interactive solving of the vehicle routing problems.Which includes man-machine interaction dynamically in computer system as follows: 1) Modifying the routes by manual relocation, and using improvement heurictic to improvethe modified solution; 2) Determining the routes that may be improved or modified by locking the other routes. 3) Interactively specifying problem-solving strategies. Finally, this paper presents the following research on vehicle routing in advanced logisticdistribution systems: 1) Generalizations of the VRPTW, such as: non-identical vehicles, multiple compartments,multicommodity, mixed pick-up and delivery, multiple time windows, split delivery, routing byorder and vehicle priority, real-time routing, multiple regions, special order assignment,transportation regulations, traffic constraints, limited capacities, limited storage or availablecapacities of warehouses,...
Keywords/Search Tags:Vehicle Routing, Heuristics, Logistic Distribution.
PDF Full Text Request
Related items