Bicriteria Traffic Assignment

The classical traffic assignment problem determines the equilibrium flows on a congested network with many infinitesimal users who choose paths to minimize their own travel times. Travelers care about cost (including tolls) as well as time, and different travelers put different weights on these two criteria. We study a bicriteria traffic assignment problem in which … Read more

A Novel Dynamic Program and Relaxations: Dual Bounds for the Capacitated Vehicle Routing Problem

State-of-the-art exact methods for solving vehicle routing problems rely on a dynamic program that enumerates the set of feasible routes and their distances. Using relaxations of the dynamic program improves these exact methods. This work is motivated by two observations. First, the dynamic program enumerates some routes with a suboptimal permutation of the locations. Second, … Read more

A Constraint Programming Approach to Real-Time Electric Vehicle Itinerary Planning with Simultaneous Activities

This article introduces the Electric Vehicle Itinerary Planning with Activities (EV-IPA) problem, which jointly optimizes vehicle routing, parallel activity scheduling, non-linear charging decisions, and time-window constraints. This tight coupling is increasingly relevant as conversational in-car assistants let drivers negotiate itineraries in natural language. However, directly embedding continuous, non-linear state-of-charge dynamics into a discrete decision space … Read more

A heuristic framework for a class of vehicle routing problems

We propose GenericILS, a general-purpose heuristic framework for generating high-quality upper bounds for Vehicle Routing Problems whose pricing subproblems are modeled, in column-generation-based exact algorithms, as resource-constrained shortest path problems described through Resource Extension Functions (REFs), the standard device for encoding constraints in branch-and-price algorithms. GenericILS reuses REFs implemented for the exact method, without a … Read more

A Data-Driven Linear Programming Model for Energy-Optimal Metro Timetables

We propose a data-driven linear programming model to compute energy-optimal timetables for networks operating under communications-based train control (CBTC); the model was developed in collaboration with Hitachi Rail Canada, the largest provider of CBTC systems worldwide. Our model minimizes the network’s effective energy consumption, defined as the total traction energy consumed by the trains minus … Read more

Optimal Refinement in Dynamic Discretisation Discovery for Continuous-Time Service Network Design

Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the … Read more

An Exact Branch-and-Cut Method for the Asymmetric Orienteering Problem with Terrain-Driven Fatigue

We present an end-to-end computational framework for provably optimal route planning in orienteering races on real terrain. The framework consists of a GIS pipeline that combines International Orienteering Federation (IOF) map symbols, a digital elevation model (DEM), and the Minetti metabolic model into a fully asymmetric cost matrix, where directional slope costs and cumulative fatigue … Read more

Optimal Batching and In-Building Delivery Routing with Capacitated Residential Parcel Lockers

Residential parcel lockers (RPLs), unlike their public counterparts, facilitate secure parcel delivery to occupants of private apartment and condominium buildings in urban areas. In this work, we consider the perspective of a last-mile parcel carrier that has access to an RPL in the lobby of a high-rise residential building. Motivated by growing e-commerce demand, we … Read more

Integrating Power Profile Optimization with Timetabling for Underground Train Networks

We study energy-efficient operation of underground train networks, where energy from regenerative braking is usable only if another train in the same electrically isolated subnetwork accelerates simultaneously. Timetabling models for this setting typically fix one velocity profile per leg and running time, which limits the matching of braking and accelerating phases. We drop this assumption … Read more