Research On Vehicle Routing Problem

With rapid development of economic globalization and information technology, logistics has become a new value-added service industry with broad prospect. It is significant to improve operation quality and performance of national economic, optimize resource allocation, enhance competitiveness of enterprises and promote development of productivity. Being an important link in logistics, transportation service is an effective way to accelerate the development of logistics by reducing transportation cost, improving transportation quality and raising transportation efficiency.Vehicle routing problem is a key problem in the optimization of transportation service, it delivery goods to the destination at lowest cost in the premise of satisfying demand of customers. During the past decades, vehicle routing problem has been paid much attention to and many research results have been obtained. The composition and classification of vehicle routing problem are introduced, and the present situation of algorithms is generalized.The objective of min-max vehicle routing problem is to minimize travelling distance of the longest route among all routes, so it is different with common vehicle routing problem. Genetic algorithm and tabu search are adopted to solve these problems. Neighbors are created with focus on the longest route in tabu search. Tests are performed on standard instances and good results are found.In the course of practical route planning and performing, new customer requests may arrive or information may change. A quick response must be made to the updated information and routes should be re-planned. This kind of problem is called dynamic vehicle routing problem. Treatment strategies are studied and system composition are analyzed for basic dynamic vehicle routing problem, and then dynamic problem are partitioned into a series of static sub-problems, which is solved by tabu search. Instances are tested with the objective to minimize total travelling distance of all routes. Compared with results obtained by other algorithms in literature, three best solutions and seven best average solutions have been found among nine instances by tabu search. Due to actual restrictions such as traffic control and customers business hours, some customers accept service by vehicle only at some time intervals, which is called time window limit. Three inter-route local search approaches including relocation, exchange and 2-opt*, and two intra-route local search approaches including 2-opt and or-opt are introduced. Combination of different approaches is adopted to solve static sub-problems. Results of test instances show that relocation is the best, 2-opt* second and exchange the worst for inter-route local search, and 2-opt is better than or-opt for intra-route local search. Effects of arrival time, distribution of geography location and time-window range on vehicle number, traveling distance and delay of all routes are also analyzed.In dynamic pickup and delivery problem with time window, the vehicle should pick up goods at pickup location and then transport the goods to the delivery location, so the pickup location of a customer must be visited before its delivery location by the same vehicle. Characteristics are described and heuristics are introduced to solve this problem. Finally basic instances are used for tests.