×

A constant approximation algorithm for the uniform a priori capacitated vehicle routing problem with unit demands. (English) Zbl 1442.90165

Summary: In this paper we introduce an a priori variant of the capacitated vehicle routing problem and provide a constant factor approximation algorithm, when the demands of customers are independent and identically distributed Bernoulli experiments. In the capacitated vehicle routing problem (CVRP) a vehicle, starting at a depot, must visit a set of customers to deliver the requested quantity of some item. The vehicle has capacity \(k\), which is the maximum number of items that the vehicle can carry at any time, but it can always return to the depot to restock. The objective is to find the shortest tour subject to these constraints. In the a priori CVRP with unit demands the vehicle has to visit a set of active customers, drawn from some distribution. Every active customer has a demand of one. The goal is to find a master tour, which is a feasible solution to the deterministic CVRP, i.e. where all customers are active. Then, given a set of active customers, the tour is shortcut to only visit those customers. The cost of the tour is the expected cost with respect to the distribution of active customers. We consider the model, where every customer is independently active with the same probability.
Let \(N\) be the number of customers. We provide an algorithm, which takes as input an a priori TSP solution with approximation factor \(\gamma\), and gives a solution to the a priori CVRP with unit demands, whose cost is at most \((1+k/N+\gamma)\) times the value of the optimal solution. Specifically, this gives an expected \(5.5\)-approximation by using the \(3.5\)-approximation to the a priori TSP from M. van Ee and R. Sitters [Algorithmica 80, No. 10, 2818–2833 (2018; Zbl 1402.90162)] and a deterministic \(8.5\)-approximation by using the deterministic \(6.5\)- approximation from A. van Zuylen [Algorithmica 60, No. 1, 110–151 (2011; Zbl 1216.68345)].

MSC:

90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
68W25 Approximation algorithms

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altinkemer, K.; Gavish, B., Heuristics for unequal weight delivery problems with a fixed error guarantee, Oper. Res. Lett., 6, 4, 149-158 (1987) · Zbl 0632.90083
[2] Altinkemer, K.; Gavish, B., Heuristics for delivery problems with constant error guarantees, Transp. Sci., 24, 4, 294-297 (1990) · Zbl 0722.90079
[3] Ando, E.; Bhattacharya, B.; Hu, Y.; Kameda, T.; Shi, Q., Selecting good a priori sequences for vehicle routing problem with stochastic demand, (Proc. 8th ICTAC (2011)), 45-61 · Zbl 1351.90022
[4] Berman, P.; Das, S. K., On the vehicle routing problem, (Proc. 9th WADS (2005)), 360-371 · Zbl 1161.68873
[5] Bertsimas, D., Probabilistic combinatorial optimization problems (1988), Massachusetts Institute of Technology, PhD thesis
[6] Bertsimas, D. J., A vehicle routing problem with stochastic demand, Oper. Res., 40, 3, 574-585 (1992) · Zbl 0764.90030
[7] Bompadre, A.; Dror, M.; Orlin, J. B., Improved bounds for vehicle routing solutions, Discrete Optim., 3, 4, 299-316 (2006) · Zbl 1112.90006
[8] Gendreau, M.; Laporte, G.; Seguin, R., Stochastic vehicle routing, Eur. J. Oper. Res., 88, 1, 3-12 (1996) · Zbl 0913.90094
[9] Gupta, A.; Nagarajan, V.; Ravi, R., Approximation algorithms for VRP with stochastic demands, Oper. Res., 60, 1, 123-127 (2012) · Zbl 1247.90050
[10] Haimovich, M.; Rinnooy Kan, A. H.G., Bounds and heuristics for capacitated routing problems, Math. Oper. Res., 10, 4, 527-542 (1985) · Zbl 0582.90030
[11] Jaillet, P., Probabilistic traveling salesman problems (1985), Massachusetts Institute of Technology, PhD thesis
[12] Jaillet, P., A priori solution of a traveling salesman problem in which a random subset of the customers are visited, Oper. Res., 36, 6, 929-936 (1988) · Zbl 0665.90096
[13] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, Eur. J. Oper. Res., 59, 3, 345-358 (1992) · Zbl 0761.90034
[14] Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, A. L., A review of dynamic vehicle routing problems, Eur. J. Oper. Res., 225, 1, 1-11 (2013) · Zbl 1292.90203
[15] Schalekamp, F.; Shmoys, D. B., Algorithms for the universal and a priori TSP, Oper. Res. Lett., 36, 1, 1-3 (2008) · Zbl 1151.90040
[16] Shmoys, D.; Talwar, K., A constant approximation algorithm for the a priori traveling salesman problem, (Proc. 13th IPCO (2008)), 331-343 · Zbl 1143.90383
[17] van Ee, M.; Sitters, R., The a priori traveling repairman problem, Algorithmica, 80, 10, 2818-2833 (2018) · Zbl 1402.90162
[18] Van Zuylen, A., Deterministic sampling algorithms for network design, Algorithmica, 60, 1, 110-151 (2011) · Zbl 1216.68345
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.