Contributed Session Fri.1.H 3010

Friday, 10:30 - 12:00 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Approximation of vehicle routing problems


Chair: Ignacio Javier Vargas



Friday, 10:30 - 10:55 h, Room: H 3010, Talk 1

Martijn van Brink
Express delivery of packages

Coauthors: Alexander Grigoriev, Tjark Vredeveld


We consider a capacitated, fixed-charge, multicommodity flow problem with indivisible commodities. The commodities are transported with trucks, which all have the same capacity, and we assume there is an unlimited number of trucks. We show that, unless P=NP, there cannot exist a polynomial time O(log K)- approximation algorithm, where K is the number of commodities. Applying randomized rounding, we obtain an approximation ratio of K+1, and we show that this ratio is tight. Next, we restrict the underlying network to cycles. We prove that the problem remains NP-hard and we develop a 4-approximation. If we assume that the total volume of all commodities is at most the capacity of a single truck, we get an integer linear programming formulation with a totally unimodular constraint matrix. Thus, we can obtain the optimal solution in polynomial time. Finally, we consider the case where we have a fixed number of commodities, and show that for 2 and 3 commodities the problem can be also solved in polynomial time.



Friday, 11:00 - 11:25 h, Room: H 3010, Talk 2

Ignacio Javier Vargas
An efficient decision making process for vehicle operations in underground mining based on a mixed-integer programming model

Coauthors: Juan M. Sepulveda, Oscar C. Vasquez


Mining operations can be seen as a vertically positioned threefold process: production, reduction and transportation. The workload of levels are pushed top-down by a plan-driven strategy, that contains the number of ore bucketfuls to be extracted at the production level. Unfortunately, the goal of minimizing makespan in the production level would be not always optimal when taking into consideration the coordination levels. In this paper, a mixed integer programming model to minimize makespan of drift workload subject to the coordination between production and reduction levels is formulated. The problem NP-hardness in strict sense is proved, the value of 2 as upper bound for polynomial algorithm in the off and on-line case is given, and 1.25-approximation algorithm for its resolution is proposed. Next, a set of decision rules obtained from the above algorithm is integrated into a simple-to-execute decision making process for LHD operators. Currently, a numerical analysis based on Chilean underground copper mine El Teniente data is being realized to explore the practical potential of the DMP proposed. The preliminary results show an average value 1.08.



Friday, 11:30 - 11:55 h, Room: H 3010, Talk 3

Enrico Bartolini
The single-vehicle dial-a-ride problem

Coauthors: Roberto Baldacci, Aristide Mingozzi


The single-vehicle dial-a-ride problem (SV-DARP) is a generalization of the traveling salesman problem with pickup and delivery (TSPPD) where the travel time between the visit of each pickup and the corresponding delivery cannot exceed a maximum ride time. The SV-DARP has several applications, e.g., in door-to-door transportation services for elderly or disabled people. We propose an exact algorithm that is based on a new mathematical formulation of the SV-DARP involving an exponential number of variables that correspond to the possible paths for each pickup-delivery pair. A valid lower bound is computed by a cut-and-column generation procedure that solves the LP relaxation of the mathematical formulation strengthened by valid inequalities. The resulting lower bound and the corresponding dual solution are used to generate all paths having reduced cost not greater than the gap between the lower bound computed and a known upper bound. The resulting integer problem is solved by means of an integer programming solver. We report on preliminary computational experiments over a large set of SV-DARP instances derived from the main TSPPD benchmark sets.


  There are three major facts that should be watched out for in all payday loans in the United States. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra, but also as part of its analogs.