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

Optimal Information Discovery in Correlated Environments: Measuring the Value of Information

We study linear combinatorial optimization problems where uncertain disruptions may affect the components (i.e., coefficients) of the objective function. To mitigate the impact of these disruptions, a planner can allocate a limited probing budget to fully reveal the status of selected components, while unprobed components status must be estimated. In contrast to settings assuming independence, … Read more

Facility Location with Decision-Dependent Scenario Probabilities: Linked Lifted Cuts and a Scenario-Decomposed Branch-and-Cut

We study two-stage facility location in which the probability of each demand scenario is an affine function of the opening decisions, so the objective multiplies a decision-dependent probability by a decision-dependent recourse value and is bilinear in the binary first stage. The standard treatment linearizes these products with McCormick envelopes over global bounds on the … Read more

String-averaging bargaining in solidarity cooperative games

We consider the situation that the grand set of all players, in a cooperative game in characteristic function form with a nonempty core, consists of recognizable subsets of players. The underlying assumption is that the players of each subset have something in common between themselves which is not shared by the players of other subsets. … Read more

Kuhn-Tucker Demand Models: Scalable Estimation and Universal Approximation

Kuhn-Tucker (KT) demand models characterize consumers’ budget allocation through the Karush-Kuhn-Tucker conditions of utility maximization. Classical specifications, including quadratic utility, are widely used to study pricing, assortment, and competition, but remain difficult to estimate from consumer data. By contrast, models designed for tractable estimation often impose restrictive assumptions on demand behavior. We address this gap … Read more

Non-contiguous satellite channel allocation under cumulative interference: A hybrid price-and-branch approach

We study a non-contiguous channelisation problem arising in multi-beam geostationary satellite communications. Carriers have heterogeneous sub- channel demands and priorities; carriers within the same beam cannot share a subchannel, while reuse across beams is permitted subject to carrier- specific cumulative-interference budgets. Demand may be partially satis- fied, with a priority-weighted objective favouring higher-priority tra!c when … 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 New Exact Algorithm for Continuous-Time Service Network Design with Splittable Deliveries

The Continuous-Time Service Network Design Problem (CTSNDP) arises in consolidation-based transportation systems, where shipments share paths in space and time to reduce cost. The CTSNDP determines minimum-cost transportation plans over a continuous-time horizon. To provide more consolidation opportunities and achieve further cost reductions, CTSNDP with Splittable Deliveries (SCTSNDP) allows each commodity to be divided into … 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