Hybrid and approximate algorithms for the dial-a-ride problem with adaptive ride times considering different service strategies

Author's Department

Mechanical Engineering Department

Find in your Library

https://doi.org/10.1080/0305215x.2022.2078813

All Authors

Sherif A. Fahmy

Document Type

Research Article

Publication Title

Engineering Optimization

Publication Date

6-15-2022

doi

10.1080/0305215x.2022.2078813

Abstract

The dial-a-ride problem (DARP) is that of satisfying a number of pickup and drop-off customer requests, using a fleet of vehicles. In real life, traffic conditions can affect expected travel times, and hence the satisfaction of rigid pickup/drop-off time windows and scheduled ride times. This article considers the DARP with customer-adaptive ride times under different service conditions and strategies. The problem is formulated as a mixed integer linear programming model that minimizes service cost and customer inconvenience. A hybrid genetic–variable neighbourhood search algorithm (GAVNS) is proposed to solve the problem. Experiments are conducted to compare the performance of GAVNS with that of an approximate column generation algorithm, and to evaluate the application of different strategies on service efficiency and customer satisfaction. The results demonstrate the efficiency of GAVNS, and that limited violations of time-window and ride-time constraints can improve the service efficiency while preserving customer satisfaction levels.

First Page

1263

Last Page

1277

This document is currently not available here.

Share

COinS