Solving Transport Problems

1An Adaptive Large Neighborhood Search Heuristic for the Green Dial-a-Ride Problem

This chapter studies the Green Dial-a-Ride Problem (G-DARP) which represents an extension of the classical Dial-a-Ride problem by considering a limited driving range of vehicles in combination with limited refueling infrastructure. In the G-DARP, a vehicle is allowed to refuel from any alternative fuel station with partial fill-up to eliminate the risk of running out of fuel during a route. This problem particularly arises for agencies and companies that employ a fleet of Alternative Fuel Vehicles (AFVs) to transport people. We present a linear mixed-integer mathematical programming formulation and propose an effective Adaptive Large Neighborhood Search (ALNS) algorithm to solve the G-DARP. Computational experiments confirm that the proposed algorithm produces high-quality solutions in a cost-effective and green manner. Moreover, the analysis shows the benefit of using partial refueling in terms of reducing the total fuel and CO₂e emissions costs compared to the use of full refueling.

1.1. Introduction

Public transportation has an overwhelming volume within the centers of today’s dynamic cities, making it increasingly difficult to manage and plan. In this respect, customers’ satisfaction is one of the major factors that should be considered in the transport planning process. Unfortunately, people with disabilities often do not have equal opportunities to benefit from the services, due to accessibility ...