Routing of Motorcycle Dispatch Deliveries on Congested and Poorly Connected Urban Networks in Lagos

Abstract

Dispatch riders carry a growing share of urban deliveries in Lagos, over a network whose traveltimes are unreliable as well as long and whose minor links fail intermittently. Routing modelsin practice optimize on mean travel times. We formulate the multi-trippickup and delivery problem with time windows for a motorcycle fleet as a mixed integer program,solve small instances exactly, and develop an adaptive large neighborhood search for the sizes asolver cannot reach, on an OpenStreetMap extract of Lagos Mainland with correlated traveltimes. Exact solution proves optimalityat six requests and one instance of eight and returns no feasible plan at twelve and beyond; theheuristic matches every proven optimum. Under Monte Carlo execution over five independentreplicates, a chance-constrained buffer raises realized on-time delivery from 87.8 to 97.0percent and cuts the ninety-ninth percentile of lateness from 49.7 to 15.1 minutes, at thecost of 4.4 percent morerider travel, planned and realized alike. The variability level at which determinismstops holding a 90 percent promise belongs to the order book, not the network. Pooled overinstances the crossing is sharp, at 0.527 times the calibrated variability level, anorigin-destination coefficient of variation of 0.170; the three order books taken separatelycross at 1.285 and 0.552 times that level, and one not at all. Thebuffered plan also wins at every level while receiving 2.7 times fewer search iterationsunder an equal wall-clock budget. The two plans therefore cannot be ranked on the deterministic objective, which is optimistic about the quantity it optimizes.