Heuristic approaches for split delivery vehicle routing problems

We propose a matheuristic approach to solve split delivery variants of the vehicle routing problem (VRP). The proposed method is based on the use of several mathematical programming components within an Iterated Local Search metaheuristic framework. In addition to well-known VRP local search heuristics, we include new types of improvement and perturbation strategies that are … Read more

Scalable Timing-Aware Network Design via Lagrangian Decomposition

This paper addresses instances of the temporal fixed-charge multi-commodity flow (tfMCF) problem that arise in a very large scale dynamic transportation application. We model the tfMCF as a discrete-time Resource Task Network (RTN) with cyclic schedule, and formulate it as a mixed-integer program. These problems are notoriously hard to solve due to their time-expanded nature, … Read more

An Adaptive Trust-Region Method Without Function Evaluations

In this paper we propose an adaptive trust-region method for smooth unconstrained optimization. The update rule for the trust-region radius relies only on gradient evaluations. Assuming that the gradient of the objective function is Lipschitz continuous, we establish worst-case complexity bounds for the number of gradient evaluations required by the proposed method to generate approximate … Read more

Solving a Multi-product, Multi-period, Multi-modal Freight Transportation Problem Using Integer Linear Programming

We consider a real-world multimodal freight transportation problem that arises in a food grain organization in India. This problem aims to satisfy the demand for a set of warehouses for different types of food grains from another set of warehouses with surplus quantities over multiple periods of time by rail and road, while minimizing the … Read more

Who Has Access to E-Commerce and When? Time-Varying Service Regions in Same-Day Delivery

Motivated by access and equity issues in e-commerce, we study the design of same-day delivery (SDD) systems under the assumption that service regions are allowed to vary over the course of the day; equivalently, that customers in different locations may have access to SDD for different lengths of time over the service day or may … Read more

On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level

It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an arbitrarily … Read more

Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within other optimization paradigms, such as integer programming and constraint programming. This paper provides a survey of the … Read more

Models and Algorithms for the Weighted Safe Set Problem

Given a connected graph G = (V, E), a Safe Set S is a subset of the vertex set V such that the cardinality of each connected component in the subgraph induced by V \ S does not exceed the cardinality of any neighbor connected component in the subgraph induced by S. When the vertices … Read more

Faster exact solution of sparse MaxCut and QUBO problems

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems-by using mathematical … Read more