ABSTRACT The Minimum Path Cover ( MPC ) problem consists of finding a minimum‐cardinality set of node‐disjoint paths that cover all nodes in a given graph. We explore a variant of the MPC problem on directed acyclic graphs (DAGs) where, given a subset of arcs, each path within the MPC should contain at least one arc from this subset. We prove that the feasibility problem is strongly ‐hard on arbitrary DAGs, but the problem can be solved in polynomial time when the DAG is the transitive closure of a path. Given that the problem may not always be feasible, our solution focuses on covering a maximum number of nodes with a minimum number of node‐disjoint paths, such that each path includes at least one arc from the predefined subset of arcs. This paper introduces and investigates two integer programming formulations for this problem. We propose several valid inequalities to enhance the linear programming relaxations, employing them as cutting planes in a branch‐and‐cut approach. The procedure is implemented and tested on a wide range of instances, including real‐world instances derived from an airline crew scheduling problem, demonstrating the effectiveness of the proposed approach.

We propose a numerically exact algorithm for solving the Bin-Packing Problem (BPP) based on a branch-price-and-cut framework combined with a pattern-enumeration method. Key to the algorithm is a novel technique for the computation of numerically safe dual bounds for the widely adopted set covering reformulation of the BPP (tightened with additional valid inequalities) with a precision that is higher than the one of general-purpose floating-point solvers. Our branch-price-and-cut algorithm also relies on an exact integer (fixed-point) label setting algorithm for solving the pricing problem associated with the tightened set-covering formulation. To the best of our knowledge, ours is the first algorithm for the BPP that is numerically exact and practical for solving large-scale instances. Extensive computational results on instances affected by notorious numerical difficulties (those of the Augmented Non-IRUP class) show that our exact algorithm outperforms all of the not numerically exact state-of-the-art algorithms based on branch-and-cut-and-price techniques that rely on a set-covering formulation of the BPP. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms − Discrete.

This study addresses the quay crane scheduling problem (QCSP), which involves scheduling a fixed number of quay cranes to load and unload containers from ships in a maritime container terminal. The objective is to minimize the completion time while adhering to precedence, safety margin, and noncrossing constraints. Efficient scheduling of quay cranes plays a crucial role in reducing the time vessels spend at terminals. To solve the QCSP, we explore different schedule directions for the quay cranes. Specifically, we consider three directions: unidirectional, where the quay cranes maintain a consistent movement direction from upper to lower bays or vice versa after initial repositioning; bidirectional, allowing the cranes to change direction once during operations; and multidirectional, permitting freely changing movement direction during operations. For the bidirectional QCSP, we propose a new compact mathematical formulation. To obtain valid lower bounds on the optimal completion time, we derive various relaxations of this new formulation based on the different schedule directions. Our solution framework employs logic-based Benders decomposition, decomposing the problem into an assignment master problem and operation-sequence slave subproblems. Extensive computational experiments using benchmark instances from existing literature and newly generated instances validate the efficiency and effectiveness of the lower bounds and the exact solution approach. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Major Program of the National Natural Science Foundation of China [Grants 72192830 and 72192831], the National Natural Science Foundation of China [Grant 72102034], and the 111 Project [Grant B16009]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0298

We present a new exact algorithm to solve a challenging vehicle routing problem with split pickups and deliveries, named as the single-commodity split-pickup and split-delivery vehicle routing problem (SPDVRP). In the SPDVRP, any amount of a product collected from a pickup customer can be supplied to any delivery customer, and the demand of each customer can be collected or delivered multiple times by the same or different vehicles. The vehicle fleet is homogeneous with limited capacity and maximum route duration. This problem arises regularly in inventory and routing rebalancing applications, such as in bike-sharing systems, where bikes must be rebalanced over time such that the appropriate number of bikes and open docks are available to users. The solution of the SPDVRP requires determining the number of visits to each customer, the relevant portions of the demands to be collected from or delivered to the customers, and the routing of the vehicles. These three decisions are intertwined, contributing to the hardness of the problem. Our new exact algorithm for the SPDVRP is a branch-price-and-cut algorithm based on a pattern-based mathematical formulation. The SPDVRP relies on a novel label-setting algorithm used to solve the pricing problem associated with the pattern-based formulation, where the label components embed reduced cost functions, unlike those classical components that embed delivered or collected quantities, thus significantly reducing the dimension of the corresponding state space. Extensive computational results on different classes of benchmark instances illustrate that the newly proposed exact algorithm solves several open SPDVRP instances and significantly improves the running times of state-of-the-art algorithms. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72222011, 71971090, 71821001, 72171112], by the Young Elite Scientists Sponsorship Program by CAST [Grant 2019QNRC001], and by the Research Grants Council of Hong Kong SAR, China [Grant 15221619]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1249 .

Motivated by rising concerns regarding global warming and traffic congestion effects, we study the time-dependent green vehicle routing problem with time windows (TDGVRPTW), aiming to minimize carbon emissions. The TDGVRPTW is a variant of the time-dependent vehicle routing problem (TDVRP) in which, in addition to the time window constraints, the minimization of carbon emissions requires determination of the optimal departure times for vehicles, from both the depot and customer location(s). Accordingly, the first exact method based on a branch-cut-and-price (BCP) algorithm is proposed for solving the TDGVRPTW. We introduce the notation of a time-dependent (TD) arc and describe how to identify the nondominated TD arcs in terms of arc departure times. In this way, we reduce infinitely many TD arcs to a finite set of nondominated TD arcs. We design a state-of-the-art BCP algorithm for the TDGVRPTW with labeling and limited memory subset row cuts, together with effective dominance rules for eliminating dominated TD arcs. The exact method is tested on a set of test instances derived from benchmark instances proposed in the literature. The results show the effectiveness of the proposed exact method in solving TDGVRPTW instances involving up to 100 customers. Summary of Contribution: Due to the environmental situation, green vehicle routing problems (GVRPs) aim to consider greenhouse gas emissions reduction, while routing the vehicles, and play a key role in transportation and logistics. Vehicle greenhouse gas emissions strongly depend on the vehicle speeds and traffic conditions which in real life vary continuously over time. To tackle these challenges, we address the time-dependent green vehicle routing problem with time windows (TDGVRPTW) aimed at reducing total carbon emissions under time-dependent travel times and time window constraints. We design an effective exact method for the TDGVRPTW based on a state-of-the-art branch-cut-and-price algorithm. The paper is both of methodological value for researchers and of interest for practitioners. For researchers, the presented algorithm is amenable for various routing constraints and provides a ground for further studies and research. For practitioners, the paper suggests insights on how the carbon emissions change based on different vehicle speed profiles. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research is supported by the National Natural Science Foundation of China [Grants 71831003, 71831006, 72171043, and 71901180] and the Fundamental Research Funds for the Central Universities [Grants N170405005 and N180704015]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/ijoc.2022.1195 .

In this paper, a new branch-and-price-and-cut algorithm is proposed to solve the one-dimensional bin-packing problem (1D-BPP). The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been extensively studied for decades. Recently, a set of new 500 test instances were proposed for the 1D-BPP, and the best exact algorithm proposed in the literature can optimally solve 167 of these new instances, with a time limit of 1 hour imposed on each execution of the algorithm. The exact algorithm proposed in this paper is based on the classical set-partitioning model for the 1DBPPs and the subset row inequalities. We describe an ad hoc label-setting algorithm to solve the pricing problem, dominance, and fathoming rules to speed up its computation and a new primal heuristic. The exact algorithm can easily handle some practical constraints, such as the incompatibility between the items, and therefore, we also apply it to solve the one-dimensional bin-packing problem with conflicts (1D-BPPC). The proposed method is tested on a large family of 1D-BPP and 1D-BPPC classes of instances. For the 1D-BPP, the proposed method can optimally solve 237 instances of the new set of difficult instances; the largest instance involves 1,003 items and bins of capacity 80,000. For the 1D-BPPC, the experiments show that the method is highly competitive with state-of-the-art methods and that it successfully closed several open 1D-BPPC instances.

International audience

ODYSSEUS 2012 was the fifth edition of the International \nWorkshop on Freight Transportation and Logistics \nthat took place in Mykonos, Greece, between May 21 and \nMay 25, 2012. The overarching aim of the Workshop was \nto provide a high-level forum for scientific exchange and \ncooperation with respect to the theory, practice, and application \nof mathematical models and optimization methodologies \nin the field of freight transportation and logistics. To disseminate \nsome of the scientific contributions presented at \nODYSSEUS 2012, we publish a special issue of Networks \nwith a focus on Vehicle Routing. This issue contains six high \nquality papers.

The traveling salesman problem with time windows (TSPTW) is the problem of finding in a weighted digraph a least-cost tour starting from a selected vertex, visiting each vertex of the graph exactly once according to a given time window, and returning to the starting vertex. This n𝒫-hard problem arises in routing and scheduling applications. This paper introduces a new tour relaxation, called ngL-tour, to compute a valid lower bound on the TSPTW obtained as the cost of a near-optimal dual solution of a problem that seeks a minimum-weight convex combination of nonnecessarily elementary tours. This problem is solved by column generation. The optimal integer TSPTW solution is computed with a dynamic programming algorithm that uses bounding functions based on different tour relaxations and the dual solution obtained. An extensive computational analysis on basically all TSPTW instances (involving up to 233 vertices) from the literature is reported. The results show that the proposed algorithm solves all but one instance and outperforms all exact methods published in the literature so far.

Abstract In the well‐known vehicle routing problem (VRP), a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two‐commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract This article proposes a new transformation of undirected arc‐routing problems into equivalent node‐routing problems, with emphasis on the transformation of Capacitated Arc Routing Problems (CARP) into Capacitated Vehicle Routing Problems (CVRP). For this last case, an analogue transformation has already been proposed in Pearn et al., where each required CARP edge is mapped onto a triplet of CVRP nodes. In our case, only two CVRP nodes are needed for every CARP required edge. The transformed instances have a structure and a dimension that make most CARP benchmarks solvable by state of the art CVRP techniques. We thus propose a general purpose transformation of arc into node‐routing problems and new results on lower bounds and exact methods for CARP instances. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 52–60 2006

Abstract In this paper, we describe a new integer programming formulation for the Traveling Salesman Problem with mixed Deliveries and Collections (TSPDC) based on a two‐commodity network flow approach. We present new lower bounds that are derived from the linear relaxation of the new formulation by adding valid inequalities, in a cutting‐plane fashion. The resulting lower bounds are embedded in a branch‐and‐cut algorithm for the optimal solution of the TSPDC. Computational results on different classes of test problems taken from the literature indicate the effectiveness of the proposed method. © 2003 Wiley Periodicals, Inc.