Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery

We propose a branch-and-cut algorithm for the VRPSPD where the constraints that ensure that the capacities are not exceeded in the middle of a route are applied in a lazy fashion. The algorithm was tested in 87 instances with 50–200 customers, finding improved lower bounds and several new optimal solutions.     

A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

A computational comparison of flow formulations for the capacitated location-routing problem

In this paper we present a computational comparison of four different flow formulations for the capacitated location-routing problem. We introduce three new flow formulations for the problem, namely a two-index two-commodity flow formulation, a three-index vehicle-flow formulation and a three-index two-commodity flow formulation. We also consider an existing two-index vehicle-flow formulation and extend it by considering new families of valid inequalities and separation algorithms. We introduce new branch-and-cut algorithms for each of the formulations and compare them on a wide number of instances. Our results show that compact formulations can produce tight gaps and solve many instances quickly, whereas three-index formulations scale better in terms of computing time.     

The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and several valid inequalities, some of which are facet defining, are introduced. Separation procedures and a branch-and-cut algorithm are developed. Computational results show that the algorithm is capable of solving to optimality instances involving up to 35 pickup and delivery requests, thus more than doubling the previous record of 15.      

A column generation approach for location-routing problems with pickup and delivery

In this paper we formulate an integer programming model for the Location and Routing Problem with Pickup and Delivery. We propose a column generation scheme and implement, for the subproblem, a label-setting algorithm for the shortest path with pickup and delivery and time windows problem. We also propose a set of heuristics to speed up this process. To validate the model, we implement the column generation scheme and test it on different instances developed in this paper. We also provide an analysis of how the costs of opening depots and the fixed cost of routes affect the optimal solution.     

An empirical study on the benefit of split loads with the pickup and delivery problem

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has been shown to have benefit for both the classic Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP). However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin–destination pairs with a load requiring service, and the clustering of origin and destination locations. We find that the magnitude of benefit is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.     

A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes

The Pickup and Delivery Problem with Shuttle routes (PDPS) is a special case of the Pickup and Delivery Problem with Time Windows (PDPTW) where the trips between the pickup points and the delivery points can be decomposed into two legs. The first leg visits only pickup points and ends at some delivery point. The second leg is a direct trip – called a shuttle – between two delivery points. This optimization problem has practical applications in the transportation of people between a large set of pickup points and a restricted set of delivery points.     

Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm

In this paper, the dynamic capacitated location-routing problem with fuzzy demands (DCLRP-FD) is considered. In the DCLRP-FD, facility location problem and vehicle routing problem are solved on a time horizon. Decisions concerning facility locations are permitted to be made only in the first time period of the planning horizon but, the routing decisions may be changed in each time period. Furthermore, the vehicles and depots have a predefined capacity to serve the customers with altering demands during the time horizon. It is assumed that the demands of customers are fuzzy variables. To model the DCLRP-FD, a fuzzy chance-constrained programming is designed based upon the fuzzy credibility theory. To solve this problem, a hybrid heuristic algorithm (HHA) with four phases including the stochastic simulation and a local search method are proposed. To achieve the best value of two parameters of the model, the dispatcher preference index (DPI) and the assignment preference index (API), and to analyze their influences on the final solution, numerical experiments are carried out. Moreover, the efficiency of the HHA is demonstrated via comparing with the lower bound of solutions and by using a standard benchmark set of test problems. The numerical examples show that the proposed algorithm is robust and could be used in real world problems.     

Decision diagrams for solving traveling salesman problems with pickup and delivery in real time

The Traveling Salesman Problem with Pickup and Delivery seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width Decision Diagrams in a branch-and-bound with and without Assignment Problem inference duals as a primal heuristic for finding good solutions within strict time budgets. We show these diagrams can be more effective than similarly structured hybrid Constraint Programming techniques for real-time decision making.     

The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method

In this paper, a strict formulation of a generalization of the classical pickup and delivery problem is presented. Here, we add the flexibility of providing the option for passengers to transfer from one vehicle to another at specific locations. As part of the mathematical formulation, we include transfer nodes where vehicles may interact interchanging passengers. Additional variables to keep track of customers along their route are considered. The formulation has been proven to work correctly, and by means of a simple example instance, we conclude that there exist some configurations in which a scheme allowing transfers results in better quality optimal solutions. Finally, a solution method based on Benders decomposition is addressed. We compare the computational effort of this application with a straight branch and bound strategy; we also provide insights to develop more efficient set partitioning formulations and associated algorithms for solving real-size problems.     

A new formulation and an exact approach for the many-to-many hub location-routing problem

An important problem of the freight industry is the parcel delivery network design, where several facilities are responsible for assembling flows from several origins, re-routing them to other facilities where the flows are disassembled and the packages delivered to their final destinations. In order to provide this service, local tours are established for the vehicles assigned to each of the processing facilities, which are then responsible for the pickup and delivery tasks. This application gives rise to the many-to-many hub location routing problem that is the combination of two well known problems: the vehicle routing problem and the single assignment hub location problem. In this work, a new formulation for this important problem is proposed and solved by a specially tailored Benders decomposition algorithm. The proposed method is robust enough to solve instances up to 100 nodes having 4 million integer variables.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.     

A survey of variants and extensions of the location-routing problem

This is a review of the literature on variants and extensions of the standard location-routing problem published since the last survey, by Nagy and Salhi, appeared in 2006. We propose a classification of problem variants, provide concise paper excerpts that convey the central ideas of each work, discuss recent developments in the field, and list promising topics for further research.     

A multi-objective mathematical model for the industrial hazardous waste location-routing problem

Industrial hazardous waste management involves the collection, transportation, treatment, recycling and disposal of industrial hazardous materials that pose risk to their surroundings. In this paper, a new multi-objective location-routing model is developed, and implemented in the Marmara region of Turkey. The aim of the model is to help decision makers decide on locations of treatment centers utilizing different technologies, routing different types of industrial hazardous wastes to compatible treatment centers, locations of recycling centers and routing hazardous waste and waste residues to those centers, and locations of disposal centers and routing waste residues there. In the mathematical model, three criteria are considered: minimizing total cost, which includes total transportation cost of hazardous materials and waste residues and fixed cost of establishing treatment, disposal and recycling centers; minimizing total transportation risk related to the population exposure along transportation routes of hazardous materials and waste residues; and minimizing total risk for the population around treatment and disposal centers, also called site risk. A lexicographic weighted Tchebycheff formulation is developed and computed with CPLEX software to find representative efficient solutions to the problem. Data related to the Marmara region is obtained by utilizing Arcview 9.3 GIS software and Marmara region geographical database.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery

This work proposes a Branch-cut-and-price (BCP) approach for the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We also deal with a particular case of the VRPSPD, known as the Vehicle Routing Problem with Mixed Pickup and Delivery. The BCP algorithm was tested in well-known benchmark instances involving up to 200 customers. Four instances were solved for the first time and some LBs were improved.     

Dynamic pickup and delivery problems

In the last decade, there has been an increasing body of research in dynamic vehicle routing problems. This article surveys the subclass of those problems called dynamic pickup and delivery problems, in which objects or people have to be collected and delivered in real-time. It discusses some general issues as well as solution strategies.     

Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care

This paper addresses a vehicle scheduling problem encountered in home health care logistics. It concerns the delivery of drugs and medical devices from the home care company’s pharmacy to patients’ homes, delivery of special drugs from a hospital to patients, pickup of bio samples and unused drugs and medical devices from patients. The problem can be considered as a special vehicle routing problem with simultaneous delivery and pickup and time windows, with four types of demands: delivery from depot to patient, delivery from a hospital to patient, pickup from a patient to depot and pickup from a patient to a medical lab. Each patient is visited by one vehicle and each vehicle visits each node at most once. Patients are associated with time windows and vehicles with capacity. Two mixed-integer programming models are proposed. We then propose a Genetic Algorithm (GA) and a Tabu Search (TS) method. The GA is based on a permutation chromosome, a split procedure and local search. The TS is based on route assignment attributes of patients, an augmented cost function, route re-optimization, and attribute-based aspiration levels. These approaches are tested on test instances derived from existing VRPTW benchmarks.     

Vehicle scheduling with combinable delivery and pickup operations

Motivated by the logistics operations in an express delivery company, we develop and study a new scheduling model. The problem seems similar to scheduling with sequence-dependent setup times and scheduling with release times, however, the ability to combine or separate the job operations makes our problem unique.     

A stochastic multi-period industrial hazardous waste location-routing problem: Integrating NSGA-II and Monte Carlo simulation

The present study extends a multi-objective mathematical model in the context of industrial hazardous waste management, which covers the integrated decisions of three levels with locating, vehicle routing, and inventory control. Analyzing these decisions simultaneously not only may lead to the most effective structure in the waste management network, but also may reduce the potential risk of managing the hazardous waste. Furthermore, because of the inherent complexity of the waste management system, uncertainty is inevitable and should be acknowledged to guarantee reliability in the decision-making process. From this perspective, the proposed model is novel in the following three aspects: (1) shifting from a deterministic to stochastic environment; (2) considering a multi-period planning horizon; and (3) incorporating the inventory decisions into the problem. The problem is formulated as a multi-objective stochastic Mixed-Integer Nonlinear Programming (MINLP) model, which can be easily converted into a MILP one. In terms of methodological contribution, a new simheuristic approach that is an integration of Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) and Monte Carlo simulation is developed to overcome the stochastic combinatorial optimization problem of this study. Our findings verify the efficiency of the proposed approach as it is able to find a high-quality solution within a relatively reasonable computational time.