Branch and Price for the Length-Constrained Cycle Partition Problem

The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP … Read more

Data-Driven Reliable Facility Location Design

We study the reliable (uncapacitated) facility location (RFL) problem in a data-driven environment where historical observations of random demands and disruptions are available. Owing to the combinatorial optimization nature of the RFL problem and the mixed-binary randomness of parameters therein, the state-of-the-art RFL models applied to the data-driven setting either suggest overly conservative solutions, or … Read more

Tactical workforce sizing and scheduling decisions for last-mile delivery

We tackle the problems of workforce sizing and shift scheduling of a logistic operator delivering parcels in the last-mile segment of the supply chain. Our working hypothesis is that the relevant decisions are affected by two main trade-offs: workforce size and shift stability. A large workforce is able to deal with demand fluctuations but incurs … Read more

Crew Scheduling and Routing Problem in Road Restoration via Branch-and-Price Algorithms

This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex post-disaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation … Read more

Integrating Public Transport in Sustainable Last-Mile Delivery: Column Generation Approaches

We tackle the problem of coordinating a three-echelon last-mile delivery system. In the first echelon, trucks transport parcels from distribution centres outside the city to public transport stops. In the second echelon, the parcels move on public transport and reach the city centre. In the third echelon, zero-emission vehicles pick up the parcels at public … Read more

A Hybrid Genetic Algorithm for Generalized Order Acceptance and Scheduling

In this paper, a novel approach is presented to address a challenging optimization problem known as Generalized Order Acceptance Scheduling. This problem involves scheduling a set of orders on a single machine with release dates, due dates, deadlines, and sequence-dependent setup times judiciously to maximize revenue. In view of resource constraints, not all orders can … Read more

Structural Insights and an IP-based Solution Method for Patient-to-room Assignment Under Consideration of Single Room Entitlements

Patient-to-room assignment (PRA) is a scheduling problem in decision support for large hospitals. This work proposes Integer Programming (IP) formulations for dynamic PRA, where either full, limited or uncertain information on incoming patients is available. The applicability is verified through a computational study. Results indicate that large, real world instances can be solved to a … Read more

A widespread belief about county splits in political districting plans is wrong

Consider the task of dividing a state into k contiguous political districts whose populations must not differ by more than one person, following current practice for congressional districting in the USA. A widely held belief among districting experts is that this task requires at least k-1 county splits. This statement has appeared in expert testimony, … Read more

Approximating the Pareto frontier for bi-objective preventive maintenance and workshop scheduling. A Lagrangean lower bounding methodology for evaluating contracting forms

Effective planning of preventive maintenance plays an important role in maximizing the operational readiness of any industrial system. We consider an operating system and a maintenance workshop governed by two stakeholders who collaborate based on a mutual contract: components of the operating system that need maintenance are sent to the maintenance workshop, where necessary maintenance … Read more

Submodular Dispatching with Multiple Vehicles

Motivated by applications in e-commerce logistics and production planning where orders (or items, or jobs) arrive at different times and must be dispatched or processed in batches, we consider a multi-vehicle dispatching problem that captures the tension between waiting for orders to arrive and the economies of scale due to batching. Our model extends the … Read more