In the electric vehicle (EV) routing and overnight charging scheduling problem, a fleet of EVs must serve the demand of a set of customers with time windows. The problem consists in finding a set of minimum cost routes and determining an overnight EV charging schedule that ensures the routes’ feasibility. Because (i) travel time and energy consumption are conflicting resources, (ii) the overnight charging operations take considerable time, and (iii) the charging infrastructure at the depot is limited, we model the problem on a multigraph where each arc between two vertices represents a path with a different resource consumption trade-off. To solve the problem, we design a branch-price-and-cut algorithm that implements state-of-the-art techniques, including the ng-path relaxation, subset-row inequalities, and a specialized labeling algorithm. We report computational results showing that the method solves to optimality instances with up to 50 customers. We also present experiments evaluating the benefits of modeling the problem on a multigraph rather than on the more classical 1-graph representation. History: Accepted by Andra Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada through the Discovery grants [Grant RGPIN-2023-03791]. It was also partially funded by HEC Montréal through the research professorship on Clean Transportation Analytics. 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.0404 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0404 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

This study addresses large-scale personnel scheduling problems in the service industry by combining mathematical programming with data mining techniques to enhance efficiency. The studied problem aims at efficiently scheduling skilled employees over a one-week planning horizon, minimizing costs while meeting diverse job demands. In service industries, shift planning is intricately tied to customer presence, leading to a multitude of potential shifts and a difficult optimization problem that cannot be easily solved using a commercial mixed-integer programming solver. Nevertheless, these problems are categorized as recurrent problems, where distinct instances share common characteristics and solution structures that differ only in a few parameters over time. We propose to use a data mining technique, namely, the \(k\) -nearest neighbors algorithm, to expedite the solution process while upholding solution quality. We suggest using schedules of past solutions to reduce the problem size. Thus, for an upcoming instance, we identify similar historical instances and streamline the enumeration of shifts to align with the comparable historical instances’ schedules. This approach allows us to solve the problem using a commercial solver within a reasonable timeframe while preserving solution quality. Moreover, our methodology offers decision-makers the flexibility to determine the extent to which they wish to scale down the problem. Our experiments conducted on instances generated from real historical data with up to 12 jobs and 252 employees, yield an average removal of up to 85.5% of decision variables. This resulted in an average speedup factor of up to 15.5, with a marginal average cost increase of approximately 1.2%.

In the last years, there has been a great interest in machine‐learning‐based heuristics for solving NP‐hard combinatorial optimization problems. The developed methods have shown potential on many optimization problems. In this paper, we present a learned heuristic for the reoptimization of a problem after a minor change in its data. We focus on the case of the capacited vehicle routing problem with static clients (i.e., same client locations) and changed demands. Given the edges of an original solution, the goal is to predict and fix the ones that have a high chance of remaining in an optimal solution after a change of client demands. This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution, while yielding a good quality solution. The proposed approach resulted in solutions with an optimality gap ranging from 0% to 1.7% on different benchmark instances within a reasonable computing time.

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Summary of Contribution: Column generation (CG) algorithms are among the most important and studied solution methods in operations research. CG algorithms are suitable to cope with large-scale problems arising from several real-life applications. The present paper proposes a generic stabilization framework to address two of the main issues found in a CG method: degeneracy in the master problem and massive instability of the dual variables. The newly devised method, called dynamic separation of aggregated rows (dyn-SAR), relies on an extended master problem that contains redundant constraints obtained by aggregating constraints from the original master problem formulation. This new formulation is solved in a column/row generation fashion. The efficacy of the proposed method is tested through an extensive experimental campaign, where we solve three different problems that differ considerably in terms of their constraints and objective function. Despite being a generic framework, dyn-SAR requires the embedded CG algorithm to be tailored to the application at hand.

We study a new variant of the vehicle routing problem, which arises in hospital-wide scheduling of physical therapists. Multiple service locations exist for patients, and resource synchronization for the location capacities is required as only a limited number of patients can be treated at one location at a time. Additionally, operations synchronization between treatments is required as precedence relations exist. We develop an innovative exact branch-price-and-cut algorithm including two approaches targeting the synchronization constraints (1) based on branching on time windows and (2) based on adding combinatorial Benders cuts. We optimally solve realistic hospital instances with up to 120 treatments and find that branching on time windows performs better than adding cutting planes. Summary of Contribution: We present an exact branch-price-and-cut (BPC) algorithm for the therapist scheduling and routing problem (ThSRP), a daily planning problem arising at almost every hospital. The difficulty of this problem stems from its inherent structure that features routing and scheduling while considering multiple possible service locations with time-dependent location capacities. We model the ThSRP as a vehicle routing problem with time windows and flexible delivery locations and synchronization constraints, which are properties relevant to other vehicle routing problem variants as well. In our computational study, we show that the proposed exact BPC algorithm is capable of solving realistic hospital instances and can, thus, be used by hospital planners to derive better schedules with less manual work. Moreover, we show that time window branching can be a valid alternative to cutting planes when addressing synchronization constraints in a BPC algorithm.

The integral column generation algorithm (ICG) was recently introduced to solve set partitioning problems involving a very large number of variables. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ICG combines the well-known column generation algorithm and a primal algorithm called the integral simplex using decomposition algorithm (ISUD). In this paper, we develop a generalized version of ICG, denoted I2CG, that can solve efficiently large-scale set partitioning problems with side constraints. This new algorithm can handle the side constraints in the reduced problem of ISUD, in its complementary problem, or in both components. Computational experiments on instances of the airline crew pairing problem (CPP) and the multidepot vehicle routing problem with time windows show that the latter strategy is the most efficient one and I2CG significantly outperforms basic variants of two popular column generation heuristics, namely, a restricted master heuristic and a diving heuristic. For the largest tested CPP instance with 1,761 constraints, I2CG can produce in less than one hour of computational time more than 500 integer solutions leading to an optimal or near-optimal solution. Summary of Contribution: In this paper, we develop a new integral column generation algorithm that can solve efficiently large-scale set partitioning problems with side constraints. The latter alter the quasi-integrality property needed for primal integral algorithms. The paper adds a methodological contribution remedying this issue. This remedy should, in our opinion, boost the use of primal exact methods, especially in the column generation context. The paper also has a computational contribution. Effectively, computational experiments on instances of the airline crew pairing problem and the multidepot vehicle routing problem with time windows are extensively discussed. We compare the proposed algorithm to basic variants of two popular column generation heuristics.

The time window assignment vehicle routing problem (TWAVRP) is the problem of assigning time windows for delivery before demand volume becomes known. This implies that vehicle routes in different demand scenarios have to be synchronized such that the same client is visited around the same time in each scenario. For TWAVRP instances that are relatively difficult to solve, we observe many similar solutions in which one or more routes have a different orientation, that is, the clients are visited in the reverse order. We introduce an edge-based branching method combined with additional components to eliminate orientation symmetry from the search tree, and we present enhancements to make this method efficient in practice. Next, we present a branch-price-and-cut algorithm based on this branching method. Our computational experiments show that addressing orientation symmetry significantly improves our algorithm: The number of nodes in the search tree is reduced by 92.6% on average, and 25 additional benchmark instances are solved to optimality. Furthermore, the resulting algorithm is competitive with the state of the art. The main ideas of this paper are not TWAVRP specific and can be applied to other vehicle routing problems with consistency considerations or synchronization requirements.

Abstract Driven by environmental considerations, regulations on vehicle emissions, and the offer of major subsidies, electric commercial vehicles (ECVs) are receiving ever stronger attention in logistics companies. Route planning for ECV fleets requires consideration of the special characteristics of ECVs, like limited driving range and the potential need to recharge en route at dedicated recharging stations. From a practical viewpoint, the number of recharge operations of each vehicle can very often be restricted to one recharge per route because (i) typical route distances in the most important application areas of ECVs, like small package shipping and food or beverage distribution, do not require more than one recharge given the current driving range of ECVs, and (ii) operations managers are very reluctant to plan vehicle routes with two or more recharges because recharging operations are perceived as unproductive idle times. We develop a simple hybrid of large neighborhood search and granular tabu search to solve the resulting electric vehicle‐routing problem with time windows and single recharge (EVRPTWS), considering the possibility of both full and partial recharge. The heuristic works on routes represented as customer sequences, and recharge operations are implicitly considered by determining the recharging position in the route, the recharging station to visit, and the amount to be recharged in optimal fashion. We discuss how our algorithm can be extended to handle nonlinear recharging times, different recharging times per station, and time‐dependent waiting times at stations. In numerical studies on EVRPTWS instances from the literature, the method provides optimal or near‐optimal solutions for instances with up to 100 customers within reasonable runtimes. Additional studies investigate the cost savings potential of partial recharges in comparison to full recharges in the presence of time‐window constraints, and examine the factors that influence this cost saving potential.

The vehicle routing problem with time windows (VRPTW) consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited within specific time windows. We introduce two enhancements for the exact solution of the VRPTW by branch-price-and-cut (BPC). First, we develop a sharper form of the limited-memory subset-row inequalities by representing the memory as an arc subset rather than a node subset. Second, from the elementary inequalities introduced by Balas in 1977, we derive a family of inequalities that dominate them. These enhancements are embedded into an exact BPC algorithm that includes state-of-the-art features such as bidirectional labeling, decremental state-space relaxation, completion bounds, variable fixing, and route enumeration. Computational results show that these enhancements are particularly effective for the most difficult instances and that our BPC algorithm can solve all 56 Solomon instances with 100 customers and 51 of 60 Gehring and Homberger instances with 200 customers.

In this article, we present a comparative study of several strategies that can be applied to achieve the so‐called elementary lower bound in vehicle routing problems, that is, the bound obtained when all positive‐valued variables in an optimal solution of the linear relaxation of the set‐partitioning formulation correspond to vehicle routes without cycles. This bound can be achieved by solving the resource‐constrained elementary shortest path problem—an ‐hard problem—as the pricing problem in a column generation algorithm, but several other strategies can be used to ultimately produce the same lower bound in less computational effort. State‐of‐the‐art algorithms for vehicle routing problems rely on the quality of this lower bound to either bound the size of the search tree in a branch‐and‐price algorithm or the complexity of an enumeration procedure used to limit the number of variables in the set‐partitioning model. We consider several strategies for imposing elementarity that involve ng ‐paths, strong degree constraints, and decremental state‐space relaxation. We compare the performance of these strategies on some selected instances of the vehicle routing problem with time windows. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 88–99. 2015

Abstract The min‐max k‐vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch‐and‐cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch‐price‐and‐cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 34–45 2014

Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithms for solving linear programs. It is often very efficient when there is very little degeneracy, but it often struggles in the presence of high degeneracy, executing many pivots without improving the objective function value. In this paper, we propose an improved primal simplex algorithm that deals with this issue. This algorithm is based on new theoretical results that shed light on how to reduce the negative impact of degeneracy. In particular, we show that, from a nonoptimal basic solution with p positive-valued variables, there exists a sequence of at most m - p + 1 simplex pivots that guarantee the improvement of the objective value, where m is the number of constraints in the linear program. These pivots can be identified by solving an auxiliary linear program. Finally, we briefly summarize computational results that show the effectiveness of the proposed algorithm on degenerate linear programs.

Abstract This article presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be derived using the variables of an equivalent compact formulation (i.e., the subproblem variables) or the master problem variables. In the first case, cuts are added to the compact formulation, either at the master level or the subproblem level, and the decomposition process is reapplied. In the second case, we show that it is possible to model inequalities defined on the master problem variables by adding new variables and constraints to the subproblem formulation. The augmented subproblem indirectly indicates that there exists an augmented compact formulation that includes these new variables and constraints. Three examples on how to apply this framework are presented: the vehicle routing problem with time windows, the edge coloring problem, and the cutting stock problem. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 301–310 2011

In many branch-and-price algorithms, the column generation pricing problem consists of computing feasible paths in a network. In this paper, we show how, in this context, path-reduced costs can be used to remove some arcs from the underlying network without compromising optimality, and we introduce a bidirectional search technique to compute these reduced costs. This arc elimination method can lead to a substantial speedup of the pricing process and the overall branch-and-price algorithm. Special attention is given to variants of shortest-path problems with resource constraints. Computational results obtained for the vehicle routing problem with time windows show the efficiency of the proposed method.

Abstract Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total distance traveled. A large number of heuristic approaches for the VRPTW have been proposed in the literature. In this article, we present a large neighborhood search algorithm that takes advantage of the power of branch‐and‐price which is the leading methodology for the exact solution of the VRPTW. To ensure diversification during the search, this approach uses different procedures for defining the neighborhood explored at each iteration. Computational results on the Solomo's and the Gehring and Homberge's benchmark instances are reported. Compared to the best known methods, the proposed algorithm produces better solutions, especially on the largest instances where the number of vehicles used is significantly reduced. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We study the problem of finding a shortest path for a car-like mobile robot with a minimal turning radius constraint. This vehicle can move either forward or backward in an unconstrained environment. By applying necessary conditions on the segment lengths of shortest paths, we partition the configuration space into elements such that a single path type is associated with 150 elements and two path types are associated with the other 11 elements. A shortest path from a fixed initial configuration to any final configuration in an element can always be found among the paths of types associated with that element. We then present an algorithm based on this partition and we give results showing that our algorithm is 15 times faster on average than the Reeds-Shepp algorithm (1990).