Approximation algorithms for solving the trip-constrained vehicle routing cover problems

Jianping Li (), Ping Yang (), Junran Lichen () and Pengxiang Pan ()
Additional contact information
Jianping Li: Yunnan University
Ping Yang: Yunnan University
Junran Lichen: Beijing University of Chemical Technology
Pengxiang Pan: Yunnan University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 3, No 6, 24 pages

Abstract: Abstract In this paper, we address the trip-constrained vehicle routing cover problem (the TcVRC problem). Specifically, given a metric complete graph $$G=(V,E;w)$$ G = ( V , E ; w ) with a set D $$(\subseteq V)$$ ( ⊆ V ) of depots, a set J $$(=V\backslash D)$$ ( = V \ D ) of customer locations, each customer having unsplittable demand 1, and k vehicles with capacity Q, it is asked to find a set $${\mathcal {C}}$$ C $$=\{C_i~|~i=1,2,\ldots ,k\}$$ = { C i | i = 1 , 2 , … , k } of k tours for k vehicles to service all customers, each tour for a vehicle starts and ends at one depot in D and permits to be replenished at some other depots in D before continuously servicing at most Q customers, i.e., the number of customers continuously serviced in per trip of each tour is at most Q (except the two end-vertices of that trip), where each trip is a path or cycle, starting at a depot and ending at other depot (maybe the same depot) in D, such that there are no other depots in the interior of that path or cycle, the objective is to minimize the maximum weight of such k tours in $${\mathcal {C}}$$ C , i.e., $$\min _{{\mathcal {C}}}\max \{w(C_i)~|~i=1,2,\ldots ,k \}$$ min C max { w ( C i ) | i = 1 , 2 , … , k } , where $$w(C_i)$$ w ( C i ) is the total weight of edges in that tour $$C_i$$ C i . Considering k vehicles whether to have common depot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MS problem) is asked to find a set $${\mathcal {C}}=\{C_i~|~i=1,2,\ldots ,k \}$$ C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, the objective is to minimize the maximum weight of such k tours in $${\mathcal {C}}$$ C ; (2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers (the TcVRC-CDMS problem) is asked to find a set $${\mathcal {C}}=\{C_i~|~i=1,2,\ldots ,k \}$$ C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, where each tour starts and ends at same depot v in D, each vehicle having its suppliers at some depots in D (possibly including v), the objective is to minimize the maximum weight of such k tours in $${\mathcal {C}}$$ C ; (3) the trip-constrained k-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply the TckTSP-NS) is asked to find a set $${\mathcal {C}}=\{C_i~|~i=1,2,\ldots ,k\}$$ C = { C i | i = 1 , 2 , … , k } of k tours mentioned-above, where each tour starts and ends at same depot v in D, each vehicle having non-suppliers, the objective is to minimize the maximum weight of such k tours in $${\mathcal {C}}$$ C . As for the main contributions, we design some approximation algorithms to solve these three aforementioned problems in polynomial time, whose approximation ratios achieve three constants $$8-\frac{2}{k}$$ 8 - 2 k , $$\frac{7}{2}-\frac{1}{k}$$ 7 2 - 1 k and 5, respectively.

Keywords: Combinatorial optimization; Trip-constrained vehicle routing covers; Min-max tour covers; Trip-constrained k-traveling salesman tours; Approximation algorithms (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01216-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:3:d:10.1007_s10878-024-01216-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01216-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().