INTRACTABILITY OF THE DIAL-A-RIDE PROBLEM AND A MULTIOBJECTIVE SOLUTION USING SIMULATED ANNEALING

Numerous techniques for generating approximate solutions have been proposed in the last decade for routing and scheduling in multi-vehicle dial-a-ride problems. While some of these techniques have mathematical foundations, it is often difficult to assess the global optimality of the generated soluti...

Full description

Saved in:
Bibliographic Details
Published in:Engineering optimization 1998-02, Vol.30 (2), p.91-123
Main Authors: BAUGH, JOHN W., KAKIVAYA, GOPALA KRISHNA REDDY, STONE, JOHN R.
Format: Article
Language:English
Subjects:
decision-support systems
Dial-a-ride problem
multiobjective programming
simulated annealing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Numerous techniques for generating approximate solutions have been proposed in the last decade for routing and scheduling in multi-vehicle dial-a-ride problems. While some of these techniques have mathematical foundations, it is often difficult to assess the global optimality of the generated solution due to the use of pure local improvement methods. In additon, most of these methods are based on a single objective, such as minimization of the number of vehicles used, and cannot account for different or competing objectives that characterize the problem. This paper proves the intractability of the dial-a-ride problem, and then describes a new approximate method based on simulated annealing that is used to solve these problems in the presence of multiple objectives.
ISSN:0305-215X
1029-0273
DOI:10.1080/03052159808941240