Narrow Results

Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log³ n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM.

We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n²) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log³ n) time parallel algorithm on a CREW PRAM.

This paper presents a new evolutionary metaheuristic for the vehicle routing problem with time windows. Ideas on multi-start local search, ejection chains, simulated annealing and evolutionary computation are combined in a heuristic that is both robust and efficient. The proposed method produces results that are on par with the current best solutions, at a fraction of the computation time needed by previous best approaches. Given the significantly lower time consumption over methods proposed previously in the literature, we consider our approach especially useful in dynamic routing problems, where decisions must be made in real-time.

CV. Jogja Transport is a company that distribute cakes “Sari Roti” in Yogyakarta, Indonesia. It has responsibility to distribute the cakes for every customer during the customers’ time windows. The distribution problem of CV. Jogja Transport belongs to Vehicle Routing Problem with Time Window (VRPTW). This paper tries to solve the problem of CV. Jogja Transport by proposing “cluster first route second” algorithm of simple heuristic method. Then the algorithm is combined with sweep algorithm for clustering the customers and Mixed Integer Linear Programming (MILP) to select the best route so that it can minimize the distance of each cluster. The result indicate that implementation of sweep algorithm and MILP can reduce the distances and the fuel up to 10.95% and the travel distance up to 2.60%.

This paper presents the design and analysis of several systems to solve Vehicle Routing Problems with Time Windows (VRPTW) limiting the search to a small number of solutions explored. All of them combine a metaheuristic technique with a route building heuristic. Simulated Annealing, different evolutionary approaches and hybrid methods have been tried. Preliminary results for each of the strategies are presented in the paper, where the combination created by some iterations of the best evolutionary approach and some iterations of SA stands out. A more exhaustive analysis of the three methods behaving better is also presented confirming the previous results. The different strategies have been implemented and tested on a series of the well-known Solomon's benchmark problems of size up to 100 customers. One of the described systems combined with a local optimization part that tries to optimize parts of a solution is being used as part of a real oil distribution system, obtaining very satisfactory results for the company.