The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

MSc Thesis #94126

Title:Vehicle Scheduling Using Constraint Satisfaction Problem Solving Techniques
Authors:Li,J
Date: 1994
Presented:
Keywords:
Abstract:In recent years, constraint-based programming has successfully automated the solution of complex combinatorial problems in many domains as diverse as planning, resource allocation, time management, personnel management, cutting optimizing, allocating radio frequencies and many others. In this scheduling system, I use the advantage of constraint-based programming to solve a complex scheduling problem, the Vehicle Routing Problem (VRP). The VRP can be described as a set of orders that have to be achieved by a limited amount of resources offered in the given time interval. This is the main difficulty of all scheduling problems - resource contention. The resources that are considered in this system are drivers and vehicles. The VRP solving strategies covered by this system vary from single-drop implementation to multi-drop implementation. The Cluster first - route second and Early start first heuristic techniques are implemented as grouping strategies. Also order-based and driver-based clustering methods are developed in the multi-drop strategy to improve the resource contention problems. The scheduler is based on th vehicle scheduling system - SCHEDULE-IT, which is under development by the Artificial Intelligence Applications Institute in Edinburgh. The aim of the scheduler is to implement a system to solve the VRP using constraint satisfaction problem based software, ILOG Solver and ILOG Schedule. Solutions can be found with different strategies. The results are discussed in this dissertation. Possible future work could entail considering more constraints and implementing more heuristic search strategies.
Download:NO ONLINE COPY

[Search These Pages] [DAI Home Page] [Comment]