This paper addresses the split-delivery vehicle routing problem with time windows (SDVRPTW) that consists of determining least-cost vehicle routes to service a set of customer demands while ...respecting vehicle capacity and customer time windows. The demand of each customer can be fulfilled by several vehicles. For solving this problem, we propose a new exact branch-and-price-and-cut method, where the column generation subproblem is a resource-constrained elementary shortest-path problem combined with the linear relaxation of a bounded knapsack problem. Each generated column is associated with a feasible route and a compatible delivery pattern. As opposed to existing branch-and-price methods for the SDVRPTW or its variant without time windows, integrality requirements in the integer master problem are not imposed on the variables generated dynamically, but rather on additional variables. An ad hoc label-setting algorithm is developed for solving the subproblem. Computational results show the effectiveness of the proposed method.
Full text
Available for:
BFBNIB, CEKLJ, IZUM, KILJ, NMLJ, NUK, ODKLJ, PILJ, PNG, SAZU, UL, UM, UPUK
We consider vehicle routing and crew scheduling problems that involve a lexicographic bi-level objective function (for instance, minimizing first the number of vehicles and second the operational ...costs) and can be solved by column generation where the subproblem is a resource constrained shortest path problem. Such problems are often modeled using a single-level objective function with a large fixed cost (weight) for ensuring the minimization of the primary objective. In this paper, we study the impact on the solution time of the fixed cost value. First, we present computational results which show that the solution time increases as the fixed cost value gets larger. Then, we develop an exact dynamic fixed cost procedure compatible with column generation that starts with a relatively small fixed cost value and increases it iteratively until optimality is reached. To prove optimality, a shortest path problem with resource constraints needs to be solved. Through a series of computational experiments on two types of problems, we show that this procedure can reduce solution times by up to 50% when compared to an approach relying on one very large fixed cost value.
Column generation is a widely used solution method for addressing several types of vehicle routing and crew scheduling problems. In these problems, the objective has often two levels. For instance, at the first level, the number of resources required (e.g., vehicles) is minimized while the second level aims at minimizing the operational costs. Typically, for modeling a two-level objective, one uses a single objective function that is defined as the first objective value multiplied by a very large fixed cost plus the second objective value. Doing so, two difficulties can arise. Firstly, the hierarchy between the objectives might not be respected when the fixed cost is not large enough. Secondly, when this cost is too large, solution times required by a column generation method increase. In this paper, we address these two possible drawbacks by developing a simple procedure that is compatible with column generation. The proposed procedure guarantees optimality with regards to the hierarchy between the objectives and substantially reduces solution times when compared to a model using a very large fixed cost.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
•We provide a time window assignment model in a VRP setting with demand uncertainty.•We develop a state-of-the-art exact branch-price-and-cut method.•We develop column generation heuristics for good ...solutions in large instances.•Numerical experiments show that using multiple demand scenarios is better than one.
In this paper we introduce the discrete time window assignment vehicle routing problem (DTWAVRP) that can be viewed as a two-stage stochastic optimization problem. Given a set of customers that must be visited on the same day regularly within some period of time, the first-stage decisions are to assign to each customer a time window from a set of candidate time windows before demand is known. In the second stage, when demand is revealed for each day of the time period, vehicle routes satisfying vehicle capacity and the assigned time windows are constructed. The objective of the DTWAVRP is to minimize the expected total transportation cost. To solve this problem, we develop an exact branch-price-and-cut algorithm and derive from it five column generation heuristics that allow to solve larger instances than those solved by the exact algorithm. We illustrate the performance of these algorithms by means of computational experiments performed on randomly generated instances.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
Vehicle routing problems (VRPs) are among the most studied problems in operations research. Nowadays, the leading exact algorithms for solving many classes of VRPs are branch-price-and-cut ...algorithms. In this survey paper, we highlight the main methodological and modeling contributions made over the years on branch-and-price (branch-price-and-cut) algorithms for VRPs, whether they are generic or specific to a VRP variant. We focus on problems related to the classical VRP—that is, problems in which customers must be served by several capacitated trucks and which are not combinations of a VRP and another optimization problem.
Full text
Available for:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
We study a rich production-routing problem with time windows arising at a catering services company. The production part consists of assembling the meals to deliver. It considers release times to ...ensure freshness of the products to be delivered and is also restricted by due times incurred by the constructed routes. Production employee shifts together with a compatible production schedule must be determined. The routing part consists of building vehicle routes that can contain multiple trips and must satisfy customer time windows and vehicle capacity. Routing and production costs, including a guaranteed minimum paid time for the drivers and the production employees, are minimized under various constraints. To solve this complex problem, we propose an exact branch-price-and-cut algorithm. We introduce a new branching rule that imposes on one branch a lower bound on the production costs. Computational results obtained on instances derived from real-world data sets show the effectiveness of this branching rule. Overall, our algorithm is able to solve to optimality instances with up to 25 orders and four products in less than two hours of computational time. To tackle larger instances involving up to 50 orders, we turn the proposed algorithm into a heuristic by avoiding a complete enumeration of the search tree and develop two other matheuristics based on this branch-price-and-cut heuristic.
The online appendices are available at
https://doi.org/10.1287/trsc.2018.0854
.
Full text
Available for:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
Effective route planning for battery electric commercial vehicle (ECV) fleets has to take into account their limited autonomy and the possibility of visiting recharging stations during the course of ...a route. In this paper, we consider four variants of the electric vehicle-routing problem with time windows: (i) at most a single recharge per route is allowed, and batteries are fully recharged on visit of a recharging station; (ii) multiple recharges per route, full recharges only; (iii) at most a single recharge per route, and partial battery recharges are possible; and (iv) multiple, partial recharges. For each variant, we present exact branch-price-and-cut algorithms that rely on customized monodirectional and bidirectional labeling algorithms for generating feasible vehicle routes. In computational studies, we find that all four variants are solvable for instances with up to 100 customers and 21 recharging stations. This success can be attributed to the tailored resource extension functions (REFs) that enable efficient labeling with constant time feasibility checking and strong dominance rules, even if these REFs are intricate and rather elaborate to derive. The studies also highlight the superiority of the bidirectional labeling algorithms compared to the monodirectional ones. Finally, we find that allowing multiple as well as partial recharges both help to reduce routing costs and the number of employed vehicles in comparison to the variants with single and with full recharges.
Full text
Available for:
BFBNIB, CEKLJ, IZUM, KILJ, NMLJ, NUK, ODKLJ, PILJ, PNG, SAZU, UL, UM, UPUK
We consider a personalized employee scheduling problem with characteristics present in retail stores consisting of multiple departments. In the setting under study, each department generally covers ...its demand in employees over the planning horizon of a week by assigning shifts to its own staff. However, the employees can also be transferred to other departments under certain conditions for executing entire shifts or parts of shifts there. The transfer feature enables to improve the overall schedule quality considerably when compared to the nontransfer case. Given the complexity of the problem, we propose a three-phase decomposition-based heuristic. In the first phase, we consider each department separately and solve a simplified version of the mono-department scheduling problems. From the obtained solutions, we deduce inter-department shifts that could potentially reduce the overall cost. This is examined in the second phase by resolving the scheduling problem of the first phase where the deduced inter-department shifts are included. In this phase, however, we decompose the scheduling problem by time, looking at each day separately. From the obtained schedules, we then devise inter-department demand curves, which specify the number of transfers between departments over time. In the third phase, we decompose the initial scheduling problem into mono-department problems using these inter-department demand curves. Consequently, our approach makes it possible to solve mono-department optimization problems to get an overall schedule while still benefiting from the employee transfer feature. In all three phases, the scheduling problems are formulated as mixed-integer linear programs. We show through extensive computational experiments on instances with up to 25 departments and 1000 employees that the method provides high-quality solutions within reasonable computation times.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but generate suboptimal ...trees in terms of accuracy. Other discrete optimization models in the literature address the optimality problem but only work well on relatively small datasets. Firat et al. (2020) proposed a column-generation-based heuristic approach for learning decision trees. This approach improves scalability and can work with large datasets. In this paper, we describe improvements to this column generation approach. First, we modify the subproblem model to significantly reduce the number of subproblems in multiclass classification instances. Next, we show that the data-dependent constraints in the master problem are implied, and use them as cutting planes. Furthermore, we describe a separation model to generate data points for which the linear programming relaxation solution violates their corresponding constraints. We conclude by presenting computational results that show that these modifications result in better scalability.
•Improved subproblem model resulting in fewer subproblems than in Firat et al. (2020).•Using data-dependent constraints as cutting planes in the master problem.•An optimization model that generates these cutting planes on demand.•A preprocessing and initialization routine that results in faster training.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
PDF
