Bag packing is widely used in logistics due to its flexibility and convenience. It is important for a firm to reduce the use of bags, not only to cut costs but also to protect the environment and promote sustainable waste management practices. In this study, we propose a novel Three-Dimensional Bag Packing Problem (3D-BGPP) which aims to pack a set of items into a set of flexible bags considering rotation. A mixed-integer linear programming model is formulated. We show that this problem is strongly NP-hard.To solve the problem more efficiently, we develop a hybrid combinatorial Benders decomposition-Beam Search algorithm (CBD-BS). This algorithm decomposes 3D-BGPP based on the combinatorial Benders decomposition, where the master problem is solved by an enhanced model and the slave problems are solved by a novel extreme point-based beam search as well as mathematical programming. Specifically, the beam search algorithm addresses the challenge of representing unused space in flexible containers and uses a limited tree search to construct promising packing solutions. The overall algorithm is further enriched with valid inequalities, variable fixing and other acceleration techniques. Computational experiments are conducted on both real order data provided by an e-commerce company and generated instances. The results show that CBD-BS can obtain high-quality solutions within seconds in small and medium scale instances, and within minutes in large scale instances.

The stack loading problem has been studied in recent years for its great impact on the container loading and unloading operations. Among different objectives of the problem considered, minimizing the total number of unordered stackings and minimizing the total number of used stacks are the two important ones, which ensure efficient loading and unloading schedules, as well as reduce storage costs, respectively. The load-bearing setting, where each container has its own weight and bearing weight, is frequently considered in box packing operations but rarely in the existing studies on the stack loading problem. However, the load-bearing constraint on containers is very important for stack loading, because safety is of paramount importance. This paper is the first study on the stack loading problem with the load-bearing constraint with an aim to minimize the number of stacks and the number of unordered stackings. We show that this problem is strongly$\mathcal{NP}$-hard even when the number of stacks is given and equals$2$. For the case where the number of stacks is given and jobs on the bottom tiers are fixed, we show that the problem can be solved by dynamic programming in pseudo-polynomial time. For the general problem, based on a two-index integer linear programming formulation and a tabu search heuristic, we develop a binary-search based matheuristic. Our experimental results demonstrate the efficiency and effectiveness of the newly developed matheuristic.Note to Practitioners—This paper is motivated by the stack loading problem and is the first study on the load-bearing limit case. The load-bearing limit is a fundamental constraint but has not been taken into account in studies in the stack loading problem. Based on ISO Standard 1496, the corner posts and corner fittings of ISO Series I containers can bear a certain amount of weight. If the total weight of the containers above exceeds the load-bearing limit of the lower container, it will hazard the load-bearing safety. This paper proposes two problem formulations: three-index formulation and two-index formulation. The three-index formulation adds the load-bearing limit to the existing stack loading problem formulation. It turns out that the traditional three-index formulation of the stack loading problem is not efficient when being used in solving the problem with load-bearing constraints. Therefore, we propose a new two-index formulation. Apart from the theoretical results, this paper proposes a matheuristic solution framework: firstly, using binary search with greedy matheuristic for feasibility checking to minimize the number of stacks, and secondly, using tabu search matheuristic to minimize the number of unordered stackings. In future research, we will apply the matheuristic to different types of container scenarios and the parallel stack loading case.

This study examines a robust flight retiming problem under time-dependent uncertainty that minimizes the worst-case total propagated delay among flights. Flight delays may spread across an airline network, negatively impacting its service quality and profitability. The usual causes of flight delay are severe weather, airport congestion, and late arrival of crew or passengers, which all vary with time. Thus, the uncertainty of such delays is generally dependent on time. In this study, we propose a novel robust time-dependent model based on an event-based framework, which can effectively capture time-dependent uncertainty with a robust optimization model. An iterative cutting-plane algorithm is developed to solve the model exactly. For comparison, we also solve the optimization model based on a traditional leg-based framework in the literature. Computational experiments show that our model outperforms the traditional model in both average and worst-case scenarios, highlighting the importance of incorporating time-dependent uncertainty into the flight retiming problem.

For an unbalanced cooperative game, its grand coalition can be stabilized by some instruments, such as subsidization and penalization, that impose new cost terms to certain coalitions. In this paper, we study an alternative instrument, referred to as cost adjustment, that does not need to impose any new coalition-specific cost terms. Specifically, our approach is to adjust existing cost coefficients of the game under which (i) the game becomes balanced so that the grand coalition becomes stable, (ii) a desired way of cooperation is optimal for the grand coalition to adopt, and (iii) the total cost to be shared by the grand coalition is within a prescribed range. Focusing on a broad class of cooperative games, known as integer minimization games, we formulate the problem on how to optimize the cost adjustment as a constrained inverse optimization problem. We prove [Formula: see text]-hardness and derive easy-to-check feasibility conditions for the problem. Based on two linear programming reformulations, we develop two solution algorithms. One is a cutting-plane algorithm, which runs in polynomial time when the corresponding separation problem is polynomial time solvable. The other needs to explicitly derive all the inequalities of a linear program, which runs in polynomial time when the linear program contains only a polynomial number of inequalities. We apply our models and solution algorithms to two typical unbalanced games, including a weighted matching game and an uncapacitated facility location game, showing that their optimal cost adjustments can be obtained in polynomial time. History: Accepted by Area Editor Andrea Lodi for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72022018 and 72091210]; the Research Grants Council of the Hong Kong SAR, China [Grant 16210020]; Hong Kong Polytechnic University [Grant P0032007]; and the Youth Innovation Promotion Association, Chinese Academy of Sciences [Grant 2021454]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0268 .

A multidepot capacitated vehicle routing problem aims to serve customers’ demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer’s demand can be served by more than one vehicle, and the total number of depots, denoted by [Formula: see text], is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of [Formula: see text] and a polynomial running time for any fixed constant [Formula: see text]. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with [Formula: see text] being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193 . 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.2021.0193 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0193 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

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 .

This study investigates a crowdsourcing last-mile delivery problem considering orders with different destinations and time windows and crowdsourced drivers with preplanned trips. In this problem, customers announce requests on a crowdsourced delivery platform to deliver orders from a depot to their destinations and crowdsourced drivers are willing to make a detour to deliver orders in exchange for rewards provided by the platform. The crowdsourced drivers have preference lists over groups of orders based on their profits and meanwhile each order has a preference list over crowdsourced drivers based on the drivers’ arrival times at the depot. According to their preference lists, to maximize profits, crowdsourced drivers need to consider routing and scheduling decisions for delivering orders. This crowdsourced driver-order matching problem is considered to be a non-cooperative game between crowdsourced drivers. A Nash equilibrium for such a non-cooperative game is a stable matching between crowdsourced drivers and orders. We propose two exact algorithms to find stable matchings and develop a heuristic algorithm to find feasible matchings for large scale problem. The results from computational experiments demonstrate that the proposed approaches are highly efficient and effective, and the matching rate of stable matching is larger than that of feasible matching. Finally, we investigate two extensions to demonstrate the applicability of our methods and also extend to a stochastic setting with random release times of orders.

For a cost-sharing cooperative game with an empty core, we study the problem of calculating a near-optimal cost allocation that satisfies coalitional stability constraints and maximizes the total cost allocated to all players. One application of such a problem is finding the minimum level of subsidy required to stabilize the grand coalition. To obtain solutions, we propose a new generic framework based on Lagrangian relaxation, which has several advantages over existing work that exclusively relies on linear programming (LP) relaxation techniques. Our approach can generate better cost allocations than LP-based algorithms, and is also applicable to a broader range of problems. To illustrate the efficiency and performance of the Lagrangian relaxation framework, we investigate two different facility location games. The results demonstrate that our new approach can find better cost allocations than the LP-based algorithm, or provide alternative optimal cost allocations for cases that the LP-based algorithm can also solve to optimality.

We study a natural extension of the classical traveling salesman problem (TSP) in the situation where multiple salesmen are dispatched from a number of different depots. As with the TSP, this problem is motivated by a large range of applications in vehicle routing. Although it is known to have a 2-approximation algorithm, whether the problem has a 3/2-approximation algorithm, as is the case with the well-known Christofides heuristic for the TSP, remains an open question. We answer this question positively by providing a 3/2-approximation algorithm for the problem with a fixed number of depots. The algorithm uses an edge exchange strategy, and its analysis hinges on a newly discovered exchange property of matroids. In addition, the algorithm is applied to multidepot extensions of other TSP variants, and we show for the first time, to our knowledge, that for these multidepot extensions the same best constant approximation ratios can be achieved as for their respective single-depot cases.

Abstract In this research, we study the capacitated traveling salesman problem with pickup and delivery (CTSPPD) on a tree, which aims to determine the best route for a vehicle with a finite capacity to transport amounts of a product from pickup points to delivery points on a tree network, such that the vehicle's total travel distance is kept to a minimum. It has several applications in logistics and is known to be NP‐hard. We develop a 2‐approximation algorithm that is a significant improvement over the best constant approximation ratio of 5 derived from existing CTSPPD literature. Computational results show that the proposed algorithm also achieves good average performance over randomly generated instances. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 179–195 2014

We study a freight proportion allocation problem (FPAP), which is a kind of transportation problem faced by MG, one of the worldpsilas leading grocery retailers. MG has a large quantity of freight for carriers to ship to Europe. During the process of freight allocation, the shipper must consider three constraints, which are minimum quantity commitment (MQC), quantity limit per carrier and cost balance among sales divisions. With these constraints,the FPAP becomes computationally intractable. By incorporating random move subroutine, we devised a special Tabu search procedure to solve this problem. Different from classical Tabu search who usually runs in the feasible regions, random move Tabu search enables the search process to enter into infeasible regions and visit disjointed feasible regions. Extensive experiments have been conducted to measure the performance of our proposed Tabu search and CPLEX solver and have shown that the random move Tabu search behaves better.

Abstract Optimization algorithms for both path and tree topology classes of the one‐commodity pickup and delivery travelling salesman problem (1‐PDTSP) are proposed in this article, which focus on minimizing the route distance to transport products among pickup and delivery customers by a single vehicle with a limited capacity of k. Each pickup customer provides one unit volume of the product while each delivery customer requires one unit volume of the product. For the path case, we propose an O(n2/ min (k,n)) algorithm for any arbitrary k, and two O(n) algorithms for k = 1 and k = ∞. For the tree case, O(n2) and O(n) algorithms are proposed for k = 1 and k = ∞, respectively. Moreover, when k is arbitrary, the problem becomes NP‐hard in the strong sense. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 24–35 2006

In this paper, we have solved the resequencing and feature assignment problem (RFAP) by an iterative search scheme, which can obtain optimum solutions for instances sized as large as that in reality. The search scheme is based on a beam search heuristic, which outperform other heuristics in previous literature. The algorithms proposed can therefore be utilized to improve the vehicle manufacturing and to benchmark the optimum or near-optimum solutions for future research