Transportation

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

Categories Scheduling, Transportation Tags , , , ,

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

Categories Combinatorial Optimization, Meta Heuristics, Transportation Tags , , ,

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

Categories Applications - OR and Management Sciences, Scheduling, Transportation Tags , , , ,

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

Categories Combinatorial Optimization, Network Optimization, Transportation

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

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation

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

Categories Production and Logistics, Transportation Tags , , ,

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

Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , ,

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

Route `Em and Count `Em: A Two-Stage Stochastic Programming Model for Anti-Submarine Operations

Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , ,

Tracking targets in undersea warfare requires successful detection by an active search asset. Maximizing detection likelihood requires strategic placement and routing of the search assets in the search region over the planning horizon. We develop a two-stage stochastic integer programming model that maximizes the expected total reward for target detections under uncertainty in target motion … Read more

Designing Autonomous Aerial Cable Car Networks for Sustainable Urban Logistics

Categories Network Optimization, Other Topics, Transportation Tags , , , ,

This paper investigates the emerging autonomous aerial cableway technology to reduce the negative impacts of urban freight transportation. We focus on the infrastructure design problem to minimize the road-transportation externalities, taking pricing, investment costs, and the physical footprint into account. The network design problem is formulated as a mixed-integer linear programming (MILP) model that explicitly … Read more