An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees Marc DufayClaire MathieuHang Zhou_2

2025-04-29 0 0 616.91KB 17 页 10玖币

侵权投诉

An Approximation Algorithm for

Distance-Constrained Vehicle Routing on Trees

Marc Dufay∗Claire Mathieu†Hang Zhou‡

Abstract

In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with

integer edge weights, a depot, a set of nterminals, and a distance constraint D. The goal is to

ﬁnd a minimum number of tours starting and ending at the depot such that those tours together

cover all the terminals and the length of each tour is at most D.

The DVRP on trees is of independent interest, because it is equivalent to the “virtual machine

packing” problem on trees studied by Sindelar et al. [SPAA’11]. We design a simple and

natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its

approximation ratio is α+ε, where α≈1.691, and in addition, that our analysis is essentially

tight. The running time is polynomial in nand D. The approximation ratio improves on the

ratio of 2 due to Nagarajan and Ravi [Networks’12].

The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction

from the tree DVRP to the bounded space online bin packing problem via a new notion of

“reduced length”.

∗IRIF and Ecole Polytechnique, France, e-mail: marc.dufay@polytechnique.edu

†CNRS Paris, France, e-mail: claire.mathieu@irif.fr.

‡Ecole Polytechnique, France, e-mail: hzhou@lix.polytechnique.fr.

arXiv:2210.03811v1 [cs.DS] 7 Oct 2022

1 Introduction

The vehicle routing problem is arguably one of the most important problems in Operations Re-

search. Books have been dedicated to vehicle routing problems, e.g., [CL12, GRW08, TV02]. Yet,

these problems remain challenging, both from a practical and a theoretical perspective. As observed

by Li, Simchi-Levi, and Desrochers [LSD92]:

Typically, two types of constraints are imposed on the route traveled by any vehicle. One

is the capacity constraint in which each vehicle cannot serve more than a given number of

customers. The second is the distance constraint: The total distance traveled by each vehicle

should not exceed a prespeciﬁed number. Depending on the system, one or both types can be

binding. Usually delivery and pick-up services are characterized by capacity constraints [. . . ],

while service systems are characterized by distance constraints (see, for example, [Ass88]). On

the latter case, the system is usually required to provide a visit of a skilled worker at customer

sites and thus the length of routes must be controlled because these are related to working

hours.

The focus of this paper is the distance constraint. In the Distance-constrained Vehicle Routing

Problem (DVRP), we are given a graph with integer edge weights, a vertex called depot, a set

of nvertices called terminals, and an integer distance constraint D. The goal is to ﬁnd a mini-

mum number of tours starting and ending at the depot such that those tours together cover all the

terminals and the length of each tour is at most D. Friggstad and Swamy [FS14] gave an O(log D

log log D)-

approximation, improving upon an O(log D)-approximation of Nagarajan and Ravi [NR12].1Ex-

perimental results were given in [LDN84].

The DVRP on trees is of independent interest, because of its relation to the Virtual Machine

(VM) packing problem [SSS11, BWSS12, RG16]. In the VM packing problem, we are given a set

of VMs that must be hosted on physical servers, where each VM consists of a set of pages and

each physical server has a capacity of Dpages. VMs running on the same physical server may

share pages. The goal is to pack the VMs onto the smallest number of physical servers. Sindelar

et al. [SSS11] observed:

Using memory traces for a mixture of diverse OSes, architectures, and software libraries, we

ﬁnd that a tree model can capture up to 67% of inter-VM sharing from these traces.

Sindelar et al. [SSS11] gave a 3-approximation for the VM packing problem on trees, and also

suggested as future work “A key direction is tightening the approximation bounds”.

It is easy to see that the VM packing problem on trees is equivalent to the DVRP on trees.

Thus the algorithm of Sindelar et al. [SSS11] is a 3-approximation for the tree DVRP. Nagarajan

and Ravi [NR12] improved the ratio of the tree DVRP to 2. When the distance bound is allowed

to be violated by an εfraction, Becker and Paul [BP19] designed a bicriteria PTAS. We observe

that the tree DVRP is strongly NP-hard (Appendix A).

In this work, we design a simple and natural approximation algorithm for the tree DVRP,

parameterized by  > 0, see Algorithm 1. The main novelty lies in the analysis of Algorithm 1.

1More precisely, Nagarajan and Ravi [NR12] designed a bicriteria O(log 1

ε),1 + ε-approximation, which could

be turned into an O(log D)-approximation by setting D=1

ε.

Our main result (Theorem 2) shows that the approximation ratio of Algorithm 1 is α+O(), where

α≈1.691 is deﬁned in Deﬁnition 1. The running time is polynomial in nand D. Interestingly, the

ratio αis best possible for Algorithm 1 (Theorem 4).

Deﬁnition 1. Let (uk)k≥1denote the following sequence:

uk=(1, k = 1,

uk−1(uk−1+ 1), k ≥2.

Let α:=

+∞

k=1

= 1.69103 . . . .

Theorem 2. For any constant ε > 0, Algorithm 1 is an (α+O())-approximation for the Distance-

constrained Vehicle Routing Problem (DVRP) on trees. Its running time is On2·D/2O(1/2).

Remark 3. It is common in vehicle routing to parameterize the running time of an algorithm by

the value of a constraint. For example, in capacitated vehicle routing with splittable demands, the

running time of the algorithms in [JS22, MZ22] is parameterized by the tour capacity.

Theorem 4. For any constant ε > 0, Algorithm 1 is at best an α-approximation for the Distance-

constrained Vehicle Routing Problem (DVRP) on trees.

It is an open question to achieve a better-than-αapproximation for the DVRP on trees. From

Theorem 4, this would require new insights in the algorithmic design.

1.1 Algorithm

Let ε > 0. Our algorithm for the DVRP is Algorithm 1. It consists of two phases, using Algorithm 2

and Algorithm 3 with Γ=1/ε2:

Phase 1: The tree is partitioned into components (Lemma 7 and Algorithm 2), where each com-

ponent can be covered with a bounded number of tours.

Phase 2: Each component is taken as an independent instance for the DVRP, which is solved

using a polynomial time dynamic program (Lemma 9 and Algorithm 3); the solution for the

whole tree is the union of the solutions for individual components.

Remark 5. As written, Algorithm 1 returns the number of tours, not the tours themselves. If

desired, by adding auxiliary information to the dynamic program of Algorithm 3 in a standard

manner, it is possible to retrieve a feasible solution whose number of tours matches the value

returned by Algorithm 1.

1.2 Overview of the Analysis

This section gives a high-level description of main new ideas in this paper.

The analysis of Algorithm 1 relies on a reduction (Theorem 16) from the DVRP on trees to the

bounded space online bin packing (Deﬁnition 14).

Algorithm 1 Approximation algorithm for the DVRP on trees. Parameter ε > 0.

Input: A tree Trooted at r, a set of terminals U, a distance constraint D

Output: number of tours in a feasible solution to cover all terminals in U

1: Γ←1/2

2: Partition the tree Tinto a set Cof components Algorithm 2

3: for each component c∈ C do

4: rc←root vertex of component c  deﬁned in Lemma 7

5: Dc←Dminus twice the distance between rand rc

6: Uc←set of terminals in Uthat belong to c

7: nc←minimum number of tours for the subproblem (c, Uc, Dc)Algorithm 3

8: return Pc∈C nc

What does bin packing have to do with DVRP on trees? The relation lies in a new notion

introduced in this paper, that of reduced lengths (Deﬁnition 10). If we consider a bin in bin

packing, its item sizes sum to at most 1. Similarly, if we consider a tour in DVRP on trees, the

reduced lengths of its subtours in components sum to at most 1 (Lemma 11).

To show the reduction (Theorem 16), we start from an instance of the tree DVRP and we

construct an instance of the bounded space online bin packing as follows. Consider the reduced

lengths of all subtours in an optimal solution. We construct an online sequence of those reduced

lengths such that reduced lengths of the subtours in the same component are consecutive in the

sequence. Then we consider a solution to the bounded space online bin packing on that sequence.

Intuitively, the bound on the number of open bins implies that bins in that solution tend to contain

only reduced lengths of the subtours from the same component. That is a desirable property

because, if a bin contains only reduced lengths of subtours in the same component, then those

subtours can be combined into a single tour (Lemma 12). Using the above intuition, we show that

the performance of Algorithm 1 for the tree DVRP is up to some negligible additive factor at least

as good as the best performance for the bounded space online bin-packing problem.

From the reduction (Theorem 16) and since the bounded space online bin packing admits an

α-competitive algorithm due to Lee and Lee [LL85], we conclude that Algorithm 1 is an (α+O(ε))

approximation for the DVRP on trees (Theorem 2).

There are several technical details along the way. For example, subtours that end in a component

and subtours that traverse a component cannot be combined in the same way, which requires

additional care in the deﬁnition of reduced lengths, see Fig. 2.

Finally, we show that the analysis in Theorem 2 on the approximation ratio of Algorithm 1 is

essentially tight by providing a matching lower bound (Theorem 4).

1.3 Organization of the Paper

In Section 2, we give the formal problem deﬁnition, preliminary results, and previous techniques. In

Section 3, we deﬁne and analyze reduced lengths. In Section 4, we prove Theorem 2 by establishing

the reduction (Theorem 16). In Section 5, we prove Theorem 4.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AnApproximationAlgorithmforDistance-ConstrainedVehicleRoutingonTreesMarcDufay*ClaireMathieuHangZhouAbstractIntheDistance-constrainedVehicleRoutingProblem(DVRP),wearegivenagraphwithintegeredgeweights,adepot,asetofnterminals,andadistanceconstraintD.Thegoalistondaminimumnumberoftoursstartingandendin...

展开>> 收起<<

An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees Marc DufayClaire MathieuHang Zhou_2.pdf

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees Marc DufayClaire MathieuHang Zhou_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: