The distance constrained multiple vehicle traveling purchaser problem

In the Distance Constrained Multiple Vehicle Traveling Purchaser Problem (DC-MVTPP) a fleet of vehicles is available to visit suppliers offering products at different prices and with different quantity availabilities. The DC-MVTPP consists in selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the distance traveled by each vehicle does not exceed a predefined upper bound. The problem generalizes the classical Traveling Purchaser Problem (TPP) and adds new realistic features to the decision problem. In this paper we present different mathematical programming formulations for the problem. A branch-and-price algorithm is also proposed to solve a set partitioning formulation where columns represent feasible routes for the vehicles. At each node of the branch-and-bound tree, the linear relaxation of the set partitioning formulation, augmented by the branching constraints, is solved through column generation. The pricing problem is solved using dynamic programming. A set of instances has been derived from benchmark instances for the asymmetric TPP. Instances with up to 100 suppliers and 200 products have been solved to optimality.     

Branch-and-price and constraint programming for solving a real-life technician dispatching problem

We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Santiago. We design optimal routes for technicians by considering travel times, soft time windows for technician arrival times at client locations, and fixed repair times. A branch-and-price algorithm was developed, using a constraint branching strategy proposed by Ryan and Foster along with constraint programming in the column generation phase. The column generation takes advantage of the fact that each technician can satisfy no more than five to six service requests per day. Different instances of the problem were solved to optimality in a reasonable computational time, and the results obtained compare favorably with the current practice.     

An exact branch-and-price algorithm for scheduling rescue units during disaster response

In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments – including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature – for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.     

A branch and price solution approach for order acceptance and capacity planning in make-to-order operations

Make-to-order (MTO) operations have to effectively manage their capacity to make long-term sustainable profits. This objective can be met by selectively accepting available customer orders and simultaneously planning for capacity. We model a MTO operation of a job-shop with multiple resources having regular and non-regular capacity. The MTO firm has a set of customer orders at time zero with fixed due-dates. The process route, processing times, and sales price for each order are given. Since orders compete for limited resources, the firm can only accept some orders. In this paper a Mixed-Integer Linear Program (MILP) is proposed to aid an operational manager to decide which orders to accept and how to allocate resources such that the overall profit is maximized. A branch-and-price (B&P) algorithm is devised to solve the MILP effectively. The MILP is first decomposed into a master problem and several sub-problems using Dantzig-Wolfe decomposition. Each sub-problem is represented as a network flow problem and an exact procedure is proposed to solve the sub-problems efficiently. We also propose an approximate B&P scheme, Lagrangian bounds, and approximations to fathom nodes in the branch-and-bound tree. Computational analysis shows that the proposed B&P algorithm can solve large problem instances with relatively short time.     

Multi-commodity supply network planning in the forest supply chain

We consider in this paper a two echelon timber procurement system in which the first echelon consists of multiple harvesting blocks and the second echelon consists of multiple mills (e.g., sawmills), both distributed geographically. Demand is put forward by mills in the form of volumes of logs of specific length and species. Due to the impact of log handling and sorting on cut-to-length harvester and forwarder productivity [Gingras, J.-F., Favreau, J., 2002. Incidence du triage sur la productivité des systèmes par bois tronçonnés. Avantage 3], the harvesting cost per unit volume increases as the number of product variety harvested per block increases. The overall product allocation problem is a large scale mixed integer programming problem with the objective of minimizing combined harvesting and aggregated transportation costs, under demand satisfaction constraints. A heuristic is first introduced then, an algorithm based on the branch-and-price approach is proposed for larger scale problems. Experimentations compare solutions found with the heuristic with the corresponding optimal solutions obtained with both Cplex (using the branch-and-bound approach) and the branch-and-price approach. Results demonstrate the good performance level of the heuristic approach for small scale problems, and of the branch-and-price approach for large scale problems.     

Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.     

Branch-and-price algorithm for the Resilient Multi-level Hop-constrained Network Design

In this work, we investigate the Resilient Multi-level Hop-constrained Network Design (RMHND) problem, which consists of designing hierarchical telecommunication networks, assuring resilience against random failures and maximum delay guarantees in the communication. Three mathematical formulations are proposed and algorithms based on the proposed formulations are evaluated. A Branch-and-price algorithm, which is based on a delayed column generation approach within a Branch-and-bound framework, is proven to work well, finding optimal solutions for practical telecommunication scenarios within reasonable time. Computational results show that algorithms based on the compact formulations are able to prove optimality for instances of limited size in the scenarios of interest while the proposed Branch-and-price algorithm exhibits a much better performance.     

A computational evaluation of a general branch-and-price framework for capacitated network location problems

The purpose of this paper is to illustrate a general framework for network location problems, based on column generation and branch-and-price. In particular we consider capacitated network location problems with single-source constraints. We consider several different network location models, by combining cardinality constraints, fixed costs, concentrator restrictions and regional constraints. Our general branch-and-price-based approach can be seen as a natural counterpart of the branch-and-cut-based commercial ILP solvers, with the advantage of exploiting the tightness of the lower bound provided by the set partitioning reformulation of network location problems. Branch-and-price and branch-and-cut are compared through an extensive set of experimental tests.     

Semiconductor lot allocation using robust optimization

In this work, the problem of allocating a set of production lots to satisfy customer orders is considered. This research is of relevance to lot-to-order matching problems in semiconductor supply chain settings. We consider that lot-splitting is not allowed during the allocation process due to standard practices. Furthermore, lot-sizes are regarded as uncertain planning data when making the allocation decisions due to potential yield loss. In order to minimize the total penalties of demand un-fulfillment and over-fulfillment, a robust mixed-integer optimization approach is adopted to model is proposed the problem of allocating a set of work-in-process lots to customer orders, where lot-sizes are modeled using ellipsoidal uncertainty sets. To solve the optimization problem efficiently we apply the techniques of branch-and-price and Benders decomposition. The advantages of our model are that it can represent uncertainty in a straightforward manner with little distributional assumptions, and it can produce solutions that effectively hedge against the uncertainty in the lot-sizes using very reasonable amounts of computational effort.     

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains challenging. In this work we provide an explanation to such challenge, by proving that when demands are given as a finite set of scenarios, solving the LP relaxation of such formulation is strongly NP-Hard. We also prove a hardness result for the case of independent normal demands.