Authors:
Stefan Edelkamp
and
Max Gath
Affiliation:
Institute for Artificial Intelligence and TZI - Center for Computing and Communication Technologies, Germany
Keyword(s):
Nested Monte-Carlo Search, Single Vehicle Pickup and Delivery Problem (PDP), Traveling Salesman Problem (TSP), Routing and Scheduling Problems.
Related
Ontology
Subjects/Areas/Topics:
Artificial Intelligence
;
Computational Intelligence
;
Evolutionary Computing
;
Formal Methods
;
Informatics in Control, Automation and Robotics
;
Intelligent Control Systems and Optimization
;
Knowledge Discovery and Information Retrieval
;
Knowledge-Based Systems
;
Machine Learning
;
Planning and Scheduling
;
Simulation and Modeling
;
Soft Computing
;
State Space Search
;
Symbolic Systems
Abstract:
Transporting goods by courier and express services increases the service quality through short transit times and satisfies individual demands of customers. Determining the optimal route for a vehicle to satisfy transport requests while minimizing the total cost refers to the Single Vehicle Pickup and Delivery Problem. Beside time and distance objectives, in real world operations it is mandatory to consider further constraints such as time windows and the capacity of the vehicle. This paper presents a novel approach to solve Single Vehicle Pickup and Delivery Problems with time windows and capacity constraints by applying Nested Monte-Carlo Search (NMCS). NMCS is a randomized exploration technique which has successfully solved complex combinatorial search problems. To evaluate the approach, we apply benchmarks instances with up to 400 cities which have to be visited. The effects of varying the number of iterations and the search level are investigated. The results reveal, that the alg
orithm computes state-of-the-art solutions and is competitive with other approaches.
(More)