Large Neighborhood Search for a Multi-Objective Dial-a-Ride Problem i...

We investigate sustainable and reliable forms of shared micro-transit services to reduce carbon dioxide emissions caused by individual transport. The service involving a fleet of small buses is designed as a feeder system to existing public transport lines and is primarily intended for commuters that need to travel regularly from remote rural areas to urban centres and back.

The underlying optimization problem is a variant of the dial-a-ride problem with three objectives: (i) maximizing the number of accepted customer transportation requests, (ii) minimizing the total distance driven (which is related to reducing CO2 emissions), and (iii) minimizing the total excess ride time of passengers (compared to shortest ride times). These conflicting objectives represent the targets of service providers (i+ii), governments (ii), and customers (i+iii).

We propose a large neighbourhood search similar to the one in Ropke and Pisinger (2006), but adapted to work with multiple objectives. To this end we maintain and steadily update a pool of non-dominated solutions, and consistently evaluate removals, insertions, and acceptance with respect to all three objectives.

A case study is performed for a rural region in Austria, based on existing micro-transit and public transport stations and reasonably generated transportation requests.