This paper studies a flow hub location problem (FHLP) stemming from recent trends in network design for e-commerce businesses. Specifically, e-commerce companies are flexible and agile in reoptimizing their logistics networks, including supplier (origin) and customer zone (destination) decisions. Furthermore, a large number of commodities (flows) and a relatively small sales volume for each product incentivize e-commerce retailers to lease warehouse spaces as hubs, yielding a large number of hub location candidates. As such, the proposed FHLP determines the origin and destination of each flow simultaneously with the hub location and flow routing decisions in contrast to the classical hub location problems, where the origins and destinations of all flows are predetermined. To solve this large-scale optimization problem, we propose an optimization algorithm that combines Lagrangian relaxation and Benders decomposition. Novel acceleration techniques, such as a clustering-empowered multicommodity Benders reformulation, learning-empowered elimination tests, and variable reduction techniques, are further developed to improve the performance and convergence of the algorithm. The efficiency of the proposed algorithm is evaluated via extensive computational experiments. The numerical results show that when compared with five other benchmark methods, the proposed algorithm can achieve optimal solutions faster for small-sized test instances and reduce optimality gaps for large-sized ones. For example, the proposed method achieves optimal solutions for a set of 10 test instances, with node sizes ranging from 225 to 450, within 20 minutes on average. In comparison, the automatic Benders decomposition method implemented in the commercial CPLEX solver achieves an average optimality gap of 2% within one hour. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0367 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0367 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract This article introduces formulations and an exact algorithm for the workforce scheduling and routing problem with park‐and‐loop. This problem extends the standard workforce scheduling and routing problem by allowing the use of walking subtours in the routes. We introduce a compact arc‐based formulation as well as a path‐based formulation with an exponential number of variables. To efficiently solve the latter, we propose a branch‐price‐and‐cut algorithm that leverages state‐of‐the‐art techniques, including a tailored version of the pulse algorithm to solve the pricing problem and the separation of subset row inequalities to strengthen the lower bound. We report on computational experiments carried out on a set of instances with up to 75 tasks adapted from the literature. The results show that our method systematically outperforms a standard MIP solver, proving optimality for 241 out of 324 instances. We also report experiments on the closely‐related service technician routing and scheduling problem, where our method delivered 12 new best solutions on a 54‐instance testbed from the literature.

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.

A recent study on the classical capacitated vehicle routing problem (CVRP) introduced an adaptive version of the widely used iterated local search paradigm, hybridized with a path-relinking (PR) strategy. The solution method, called adaptive iterated local search (AILS)-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances suggest that PR is too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an AILS combined with mechanisms to handle large CVRP instances, called AILS-II. The computational cost of this implementation is reduced, whereas the algorithm also searches the solution space more efficiently. AILS-II is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best-known solutions. Moreover, AILS-II consistently outperforms the state of the art on larger instances with up to 30,000 vertices. History: Accepted by Ted Ralphs, Area Editor for Software Tools. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Software Tools for Vehicle Routing. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 2013/07375-0, 2019/22067-6, and 2022/05803-3] and the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 309385/2021-0 and 403735/2021-1]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0106 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0106 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

This work investigates lot sizing with component substitution under demand uncertainty. The integration of component substitution with lot sizing in an uncertain demand context is important because the consolidation of the demand for components naturally allows risk-pooling and reduces operating costs. The considered problem is relevant not only in a production context, but also in the context of distribution planning. We propose a stochastic programming formulation for the static–dynamic type of uncertainty, in which the setup decisions are frozen but the production and consumption quantities are decided dynamically. To tackle the scalability issues commonly encountered in multistage stochastic optimization, this paper investigates the use of stochastic dual dynamic programming (SDDP). In addition, we consider various improvements of SDDP, including the use of strong cuts, the fast generation of cuts by solving the linear relaxation of the problem, and retaining the average demand scenarios. Finally, we propose two heuristics, namely, a hybrid of progressive hedging with SDDP and a heuristic version of SDDP. Computational experiments conducted on well-known instances from the literature show that the heuristic version of SDDP outperforms other methods. The proposed method can plan with up to 10 decision stages and 20 scenarios per stage, which results in 2010 scenario paths in total. Moreover, as the heuristic version of SDDP can replan to account for new information in less than a second, it is convenient in a dynamic context. Summary of Contribution: We believe our paper is suitable for the mission and scope of IJOC because we design efficient algorithms to solve an operations research problem. More precisely, we investigate the use of stochastic dual dynamic programming (SDDP) for lot sizing with component substitution under demand uncertainty. In this work, we consider the static–dynamic decision framework, and a good approximation of the expected costs in this context requires us to solve the problem with a large number of scenarios of future demand. As solving the considered problem is computationally intensive, we investigate the use of SDDP, which decomposes the problem per decision stage. We study several enhancements of SDDP, such as the use of strong cuts, the incorporation of a lower bound computed with the average demand scenario, the multicut version of SDDP, and scenario sampling with randomized quasi–Monte Carlo. Despite these improvements, the convergence of SDDP remains slow. Consequently, we propose a heuristic version of SDDP and a hybrid of progressive hedging and SDDP. We present the results of an extensive computational study performed on well-known instances from the literature. The results show that the heuristic SDDP outperforms the hybrid of progressive hedging with SDDP and state-of-the-art methods from the literature. Besides, our analysis shows that component substitution can pool the risk, and it allows maintaining the same service level with less inventory. The presented methodology can be used by practitioners to size their production lots, and subsequent researchers can build upon our results to consider uncertainty in other parameters, such as lead times, yields, and production capacities. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by Mitacs and the Institut de Valorisation des Données (IVADO). Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.1215 .

Abstract This article introduces the consistent production routing problem in a setting with multiple plants and products. The problem consists in finding minimum‐cost production‐routing plans that also meet specific consistency requirements. In our context, consistency is defined as the degree to which some specified features of the solution remain invariant over time. We consider four forms of consistency, namely: driver, source, product, and plant consistency. For each of these consistency requirements, there is a target maximum value defining the decision‐maker's tolerance to deviations from a perfectly consistent solution. These targets are enforced as soft constraints whose violations need to be minimized when optimizing the integrated production and routing plan. We present a mathematical formulation for the problem and an exact branch‐and‐cut algorithm, enhanced with valid inequalities and specific branching priorities. We also propose a heuristic solution method based on iterated local search and several mathematical programming components. Experiments on a large benchmark set of newly introduced instances show that the enhancements substantially improve the performance of the exact algorithm and that the heuristic method performs robustly for production routing problems with different consistency requirements as well as for standard versions of the problem. We also analyze the cost‐consistency trade‐off of the solutions, confirming that it is possible to impose consistency without excessively increasing the cost. The results also reveal the impact of the first time period when optimizing and measuring the consistency features we study.

While the joint optimization of production and outbound distribution decisions in a manufacturing context have been intensively studied in the past decade, the integration of production, inventory, and inbound transportation from suppliers have received much less attention despite its practical relevance. This paper aims to fill the gap by introducing a general model for the assembly routing problem (ARP), which consists of simultaneously planning the assembly of a finished product at a plant and the routing of vehicles collecting materials from suppliers to meet the inventory requirements imposed by the production. We formulate the problem as a mixed-integer linear program and we propose a three-phase decomposition matheuristic that relies on the iterative solution of different subproblems. The first phase determines a setup schedule while the second phase optimizes production quantities, supplier visit schedules and shipment quantities. The third phase solves a vehicle routing problem for each period in the planning horizon. The algorithm is flexible, and we show how it can also be used to solve two well-known outbound distribution problems related to the ARP: the production routing problem and the inventory routing problem. Using the same parameter setting for all problems and instances, we obtain 781 new best-known solutions out of 2,628 standard IRP and PRP test instances. In particular, on large-scale multivehicle instances, the new algorithm outperforms specialized state-of-the-art heuristics for these two problems. The online appendix is available at https://doi.org/10.1287/ijoc.2018.0817 .

We consider the dynamic facility location problem with generalized modular capacities, a multiperiod facility location problem in which the costs for capacity changes may differ for all pairs of capacity levels. The problem embeds a complex cost structure and generalizes several existing facility location problems, such as those that allow temporary facility closing or capacity expansion and reduction. As the model may become very large, general-purpose mixed-integer programming (MIP) solvers are limited to solving instances of small to medium size. In this paper, we extend the generalized model to the case of multiple commodities. We propose Lagrangian heuristics, based on subgradient and bundle methods, to find good quality solutions for large-scale instances with up to 250 facility locations and 1,000 customers. To improve the final solution quality, a restricted MIP model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian-based heuristics provide highly reliable results for all problem variants considered. They produce good quality solutions in short computing times even for instances where state-of-the-art MIP solvers do not find feasible solutions. The strength of the formulation also allows the method to provide tight bounds on the optimal value. Data and the online appendix are available at https://doi.org/10.1287/ijoc.2016.0738 .

The inventory routing problem (IRP) and the production routing problem (PRP) are two difficult problems arising in the planning of integrated supply chains. These problems are solved in an attempt to jointly optimize production, inventory, distribution, and routing decisions. Although several studies have proposed exact algorithms to solve the single-vehicle problems, the multivehicle aspect is often neglected because of its complexity. We introduce multivehicle PRP and IRP formulations, with and without a vehicle index, to solve the problems under both the maximum level (ML) and order-up-to level (OU) inventory replenishment policies. The vehicle index formulations are further improved using symmetry breaking constraints; the nonvehicle index formulations are strengthened by several cuts. A heuristic based on an adaptive large neighborhood search technique is also developed to determine initial solutions, and branch-and-cut algorithms are proposed to solve the different formulations. The results show that the vehicle index formulations are superior in finding optimal solutions, whereas the nonvehicle index formulations are generally better at providing good lower bounds on larger instances. IRP and PRP instances with up to 35 customers, three periods, and three vehicles can be solved to optimality within two hours for the ML policy. By using parallel computing, the algorithms could solve the instances for the same policy with up to 45 and 50 customers, three periods, and three vehicles for the IRP and PRP, respectively. For the more difficult IRP (PRP) under the OU policy, the algorithms could handle instances with up to 30 customers, three (six) periods, and three vehicles on a single core machine, and up to 45 (35) customers, three (six) periods, and three vehicles on a multicore machine.

In this paper we present an exact algorithm for the capacitated location-routing problem (CLRP) based on cut-and-column generation. The CLRP is formulated as a set-partitioning problem that also inherits all of the known valid inequalities for the flow formulations of the CLRP. We introduce five new families of inequalities that are shown to dominate some of the cuts from the two-index formulation. The problem is solved by column generation, where the subproblem consists in finding a shortest path of minimum reduced cost under capacity constraints. We first use the two-index formulation for enumerating all of the possible subsets of depot locations that could lead to an optimal solution of cost less than or equal to a given upper bound. For each of these subsets, the corresponding multiple depot vehicle routing problem is then solved by means of column generation. The results show that we can improve the bounds found in the literature, solve to optimality some previously open instances, and improve the upper bounds on some other instances.

The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any delivery. In addition, items can be loaded on multiple stacks in the vehicle, and each stack must obey the last-in-first-out policy. The problem consists of finding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthenings of these constraints, which are used within a branch-and-cut algorithm. Computational results performed on instances from the literature show that the algorithm outperforms existing exact algorithms. Instances with up to 28 requests (58 nodes) have been solved to optimality.

This paper introduces a hybrid algorithm for the dynamic dial-a-ride problem in which service requests arrive in real time. The hybrid algorithm combines an exact constraint programming algorithm and a tabu search heuristic. An important component of the tabu search heuristic consists of three scheduling procedures that are executed sequentially. Experiments show that the constraint programming algorithm is sometimes able to accept or reject incoming requests, and that the hybrid method outperforms each of the two algorithms when they are executed alone.

Abstract This article studies a transportation problem in a multimodal network with shipment consolidation options. A freight forwarder can use a mix of flexible‐time and scheduled transportation services. Time windows are a prominent aspect of the problem. For instance, they are used to model pickup and delivery time slots. The various features of the problem can be described as elements of a digraph and their integration leads to a holistic graph representation. This allows an origin‐destination integer multi‐commodity flow formulation with nonconvex piecewise linear costs, time windows, and side constraints. Column generation algorithms are designed to compute lower bounds. These column generation algorithms are also embedded within heuristics aimed at finding feasible integer solutions. Computational results with real‐life data are presented and show the efficacy of the proposed approach. © 2010 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehicle must serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before the corresponding delivery. This article addresses a variant of the TSPPD in which pickups and deliveries must be performed according to a Last‐In First‐Out (LIFO) policy. We propose three mathematical formulations for this problem and several families of valid inequalities which are used within a branch‐and‐cut algorithm. Computational results performed on test instances from the literature show that most instances with up to 17 requests can be solved in less than 10 min, whereas the largest instance solved contains 25 requests. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

This paper shows how local branching can be used to accelerate the classical Benders decomposition algorithm. By applying local branching throughout the solution process, one can simultaneously improve both the lower and upper bounds. We also show how Benders feasibility cuts can be strengthened or replaced with local branching constraints. To assess the performance of the different algorithmic ideas presented in this hybrid solution approach, extensive computational experiments were performed on two families of network design problems. Numerical results clearly illustrate their benefits.

Abstract The Steiner tree problem with revenues, budget and hop constraints is a variant of the Steiner tree problem with two main modifications: (a) besides the costs associated with arcs, there are also revenues associated with the vertices, and (b) there are additional budget and hop constraints, which impose limits on the total cost of the network and on the number of edges between any vertex and the root, respectively. This article introduces and compares several mathematical models for this problem and describes two branch‐and‐cut algorithms, which solve to optimality instances with up to 500 vertices and 625 edges. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

This paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a last-in-first-out (LIFO) order. We introduce three new local search operators for this problem, which are then embedded within a variable neighborhood search heuristic. We evaluate the performance of the heuristic on data adapted from TSPLIB instances.

Abstract In the pickup and delivery problem with time windows (PDPTW), capacitated vehicles must be routed to satisfy a set of transportation requests between given origins and destinations. In addition to capacity and time window constraints, vehicle routes must also satisfy pairing and precedence constraints on pickups and deliveries. This paper introduces two new formulations for the PDPTW and the closely related dial‐a‐ride problem (DARP) in which a limit is imposed on the elapsed time between the pickup and the delivery of a request. Several families of valid inequalities are introduced to strengthen these two formulations. These inequalities are used within branch‐and‐cut algorithms which have been tested on several instance sets for both the PDPTW and the DARP. Instances with up to eight vehicles and 96 requests (194 nodes) have been solved to optimality. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 258–272 2007

In the generalized quadratic assignment problem (GQAP) we are given n weighted facilities, m capacitated sites, a traffic intensity matrix between facilities, a distance matrix between sites, unit traffic costs, and assignment costs of facilities to sites. The aim is to determine an assignment of facilities to sites so that the sum of assignment and traffic costs is minimized and the total weight of all facilities assigned to the same site does not exceed the site capacity. The GQAP is a generalization of the quadratic assignment problem (QAP) in which n = m and exactly one facility must be assigned to each site. The problem has applications in container yard management and in the assignment of equipment to manufacturing sites. This article describes a memetic heuristic for the GQAP, as well as an integer linear programming formulation that can be solved by CPLEX for small instances. For larger instances, feasible solutions can be obtained by a truncated branch-and-bound procedure. Computational experiments show that on small instances the proposed heuristic always yields an optimal solution; on larger instances it always outperforms the truncated branch-and-bound algorithm.

We propose a tabu search heuristic capable of solving three well-known routing problems: the periodic vehicle routing problem, the periodic traveling salesman problem, and the multi-depot vehicle routing problem. Computational experiments carried out on instances taken from the literature indicate that the proposed method outperforms existing heuristics for all three problems. © 1997 John Wiley & Sons, Inc. Networks 30: 105–119, 1997