De-Cranking Heuristic Method for Vehicle Routing Problems

Abstract

The field of vehicle routing is currently growing rapidly because of many actual applications in truckload and less-than-truckload trucking, courier services, door-to-door services and many other problems that generally hinder the optimization of transportation costs in a logistics network. The rapidly increasing number of customers in such a network has caused problems such as difficulty in cost optimization in terms of getting a global optimum solution in an acceptable time. Fast algorithms are needed to find sufficient solutions in a limited time that can be used for real-time scheduling.

This dissertation will discus about heuristics to solve the vehicle routing problems (VRP) in static and dynamic contexts. The solutions for VRP can be obtained exact or heuristic ways. Specially, an introduction to De-Cranking heuristic method, which is an effective improvement of the problem solving method to solve the VRP, will be drawn out. The goal is to minimize the transportation cost for motor-elements fleet such as vehicles, truck, lorry, train, AGV and etc. moving inside warehouses or touring around a planed ordered list of locations

data frames moving on networks and etc. by rerouting and re-dispatching at any time occurring new requests, and/or changing overtime traffic condition on the itineraries.

As any heuristic methods for the VRP, a started solution should be initialized before applying any adjustment procedures from the methods. That solution may be taken from random or reasonable methods. Even with random methods need also some reasonable ones to generate out which related to something called Monte Carlo Methods. This dissertation will not investigate to random methods but will introduce some useful and effective heuristic methods (reasonable ones) for the VRP.

Beginning with the nearest neighbor method, which is classical immediate selecting one next location with lowest cost through all solution until shaping a complete route solution, and then, developing an algorithm in which generalizing the string of location involving in checking lowest cost selection with a given length L. It is called nearest L-neighbor method (NLNM). This method is utilized to obtain the first stage route solution.

In second stage, De-Cranking procedure will release the "cranky energy" if any appearing in the partial route of the first-stage solution, but conserving complete routing to all locations, to get a better route which may not be global optimal solution but near or sometime coincide to it.

The dissertation also gives elements, processes and simulation methods such as lexicographic ordering, traversal the multi-branch tree and so on, from which some exact methods and heuristic method could be developed base on dependently or separately, to solve a class of combinatorial optimization problems which VRP is a representative one.

crews, waiters/waitresses in large custom "Ph□" restaurant and etc. moving to server guests