Heuristics for New Problems Arising in the Transport of People and Goods

Abstract

The Vehicle Routing Problem (VRP) and its numerous variants are amongst the most widely studied in the entire Operations Research literature, with applications in fields includ- ing supply chain management, journey planning and vehicle scheduling. In this thesis, we focus on three problems from two fields with a wide reach; the design of public trans- port systems and the robust routing of delivery vehicles. Each chapter investigates a new setting, formulates an optimization problem, introduces various solution methods and presents computational experiments highlighting salient points. The first problem involves commuters who use a flexible shuttle service to travel to a main transit hub, where they catch a fixed route public transport service to their true destina- tion. In our variant, passengers must forgo some of the choices they had in previous ver- sions; the service provider chooses the specific hub passengers are taken to (provided all relevant timing constraints are satisfied). This introduces both complexities and opportu- nities not seen in other VRP variants, so we present two solution methods tailored for this problem. An extensive computational study over a range of networks shows this flexibility allows significant cost savings with little impact on the quality of service received. The second problem involves dynamic ridesharing schemes and one of their most per- sistent drawbacks: the requirement to attract a large number of users during the start up phase. Although this is influenced by many factors, a significant consideration is the per- ceived uncertainty around finding a match. To address this, the service provider may wish to employ a small number of their own private drivers, to serve riders who would oth- erwise remain unmatched. We explore how this could be formulated as an optimization problem and discuss the objectives and constraints the service provider may have. We then describe a special structure inherent to the problem and present three different so- lution methods which exploit this. Finally, a broad computational study demonstrates the potential benefits of these dedicated drivers and identifies environments in which they are most useful. The third problem comes from the field of logistics and involves a large delivery firm serving an uncertain customer set. The firm wishes to build low cost delivery routes that remain efficient after the appearance and removal of some customers. We formulate this problem and present a heuristic which is both computationally cheaper and more versatile than comparative exact methods. A wide computational study illustrates our heuristic’s predictive power and its efficacy compared to natural alternative strategies.