Optimization and Machine Learning Methods for Solving Combinatorial Problems in Urban Transportation

This dissertation investigates three applications of emerging technologies for urban trans- portation. In the first chapter, we design a new market for fractional ownership of au- tonomous vehicles (AVs), in which an AV is co-leased by a group of individuals. We present a practical iterative auction based on the combinatorial clock auction to match the interested customers together and determine their payments. In designing such an auction, we con- sider continuous-time items (time slots) which are defined by bidders, and naturally exploit driverless mobility of AVs to form co-leasing groups. To relieve the computational burdens of both bidders and the auctioneer, we devise user agents who generate packages and bid on behalf of bidders. Through numerical experiments using the California 2010–2012 travel survey, we test the performance of the auction design. In the second chapter, we propose a reinforcement learning approach for nightly offline rebalancing operations in free-floating electric vehicle sharing systems (FFEVSS). Due to sparse demand in a network, FFEVSS requires relocation of electrical vehicles (EVs) to charging stations and demander nodes, which is typically done by a group of drivers. A shuttle is used to pick up and drop off drivers throughout the network. The objective of this study is to solve the shuttle routing problem to finish the rebalancing work in minimal time. We consider a reinforcement learning framework for the problem, in which a central controller determines the routing policies of a fleet of multiple shuttles. We deploy a policy gradient method for training recurrent neural networks and compare the obtained policy results with heuristic solutions. In the final problem, the application of the tandem of drone and truck for last mile delivery is proposed. To take advantage of the different properties of drone and truck to deliver goods to customers, an efficient routing algorithm is introduced based on reinforcement learning. The proposed method produces the routing policies of both drone and truck that identifies customers served by drone, customers served by turck and includes recharging nodes for drone. In this study we present, a novel model, called hybrid, consisting of an attention encoder and a LSTM decoder to effectively route both drone and truck