In this paper, we propose a mathematical model and an adaptive large neighborhood search to solve a two-tiered transportation problem. This problem arises in a prospective study that aims at designing an innovative distribution system for goods in congested city cores. In the first tier, goods are transported in city buses from a consolidation and distribution center to a set of bus stops. The main idea is to use the buses spare capacity to drive the goods to the city core. In the second tier, final customers are distributed by a fleet of near-zero emissions city freighters. This system requires transferring the goods from buses to city freighters at the bus stops. We model the corresponding optimization problem as a variant of the pickup and delivery problem with transfers and solve it with an adaptive large neighborhood search. To evaluate its results, lower bounds are calculated with a column generation approach. The algorithm is assessed on data sets derived from a field study in the medium-sized city of La Rochelle in France.

The pickup and delivery problem (PDP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the PDP where requests can change vehicle during their trip. The transfer is made at specific locations called “transfer points.” The corresponding problem is called the pickup and delivery problem with transfers (PDPT). Solving the PDPT leads to new modeling and algorithmic difficulties. We propose new heuristics capable of efficiently inserting requests through transfer points. These heuristics are embedded into an adaptive large neighborhood search. We evaluate the method on generated instances and apply it to the transportation of people with disabilities. On these real-life instances we show that the introduction of transfer points can bring significant improvements (up to 9%) to the value of the objective function.