A new heuristic for the passenger pick-up and drop-off problem

Abstract

In this thesis, we addrcss the Passenger Pick-up and Drop-off Problem (PPDP). In PPDP. k vehicles transport n passengers from their pick-up locations to their Drop-off locntions. The vehicles stay at a start depot at beginning and go to an end depot after all services. Each vehicle has a limited capacity and each passenger may require different sp;lce in the vehicle. The objective is to schedule the vehicles to minimize the total traveling cost and satisfy all passengers. Our focus here is on the development of solution methodology and algorithms for a PPDP with one vehicle. We propose a new algorithm: the Grouping Method (G-M), to solve this problem. The G-M considers the precedence relationship as well as distance among nodes. Comparison with some general algorithms (e.g. Branch and Bound, Nearest Neighbor and Exchange) is done through computational experiments. The results show that the Grouping Method is very effective and efficient.

Date of Award	1996
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology