A thesis submitted in partial fulfillment of the requirement for the degree of Master of Engineering, School of Advanced Technologies

This study presented an application of an integrated system of an heuristic procedure with the Geographic Information System (GIS) to solve the routing and scheduling problem that exists in the delivery business. Instead of using one-system alone, merging two systems to enhance the problem solving performance is desirable for this study. In practice, customer calls the call center requesting services and each customer demand requires an immediately service. Then routing and scheduling is done in real time; therefore, when a new demand arrives, at least one schedule has to be changed in order to serve this new demand. The problem is classified into the vehicle routing problem with time window (VRPTW) and involves the design of a set of minimum cost routes. Firstly, the exact procedure was employed using LINGO. Secondly, a heuristic (approximation) procedures, applying the saving insertion, or-opt and 2*-opt procedures were proposed. The study of both algorithms was made to compare the performance of these procedures. The heuristic is used in the integrated system because its computational time is less expensive. The Geographic Information System provides the candidate depots for each newly arrived customer and the distance between customers and depots. These results are provided to the heuristic algorithm for routing and scheduling. Results of the tests showed that the integrated system is possible, using GIS as a tool to enhance and to provide correct and timely information into the heuristic procedure. The heuristic procedure also provided the good quality solutions within less runtime.

Thesis (M.Eng.) - Asian Institute of Technology, 2000