Approximation Algorithms for the Load-Balanced Capacitated Vehicle Routing Problem
- PDF / 615,857 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 252 Views
Approximation Algorithms for the Load-Balanced Capacitated Vehicle Routing Problem Haniyeh Fallah1 · Farzad Didehvar1 · Farhad Rahmati1 Received: 17 August 2019 / Revised: 13 June 2020 / Accepted: 14 July 2020 © Iranian Mathematical Society 2020
Abstract We study the load-balanced capacitated vehicle routing problem (LBCVRP): the problem is to design a collection of tours for a fixed fleet of vehicles with capacity Q to distribute a supply from a single depot between a number of predefined clients, in a way that the total traveling cost is a minimum, and the vehicle loads are balanced. The unbalanced loads cause the decrease of distribution quality especially in business environments and flexibility in the logistics activities. The problem being NP-hard, we propose two approximation algorithms. When the demands are equal, we present a ((1 − Q1 )ρ + 23 )−approximation algorithm that finds balanced loads. Here, ρ is the approximation ratio for the known metric traveling salesman problem (TSP). This result leads to a 2.5 − Q1 approximation ratio for the tree metrics since an optimal solution can be found for the TSP on a tree. We present an improved 2−approximation algorithm. When the demands are unequal, we focus on obtaining approximate solutions since finding balanced loads is NP-complete. We propose an algorithm that provides a 4−approximation for the balance of the loads. We assume a second approach to get around the difficulties of the feasibility. In this approach, we redefine and convert the problem into a multi-objective problem. The algorithm we propose has a 4 factor of approximation. Keywords Capacitated vehicle routing problem · Load-balanced capacitated vehicle routing problem · Approximation algorithms · Fairness
Communicated by Sohrab Effati.
B
Farzad Didehvar [email protected] Haniyeh Fallah [email protected] Farhad Rahmati [email protected]
1
Department of Mathematics and Computer Science, Amirkabir University of Technology, P. O. Box 15875-4413, Tehran, Iran
123
Bulletin of the Iranian Mathematical Society
Mathematics Subject Classification 68W25 · 68W40
1 Introduction 1.1 Problem Definition The capacitated vehicle routing problem (CVRP) is a well-known and fundamental problem in the domain of operations research. It has many applications that are mostly related to transportation, logistics industry, communications, manufacturing, military and relief systems, etc. The CVRP is a graph problem that can be defined as follows: the quantity dv should be delivered to the client v(v = 1, ..., n) from a single depot using a vehicle fleet with capacity Q. A CVRP solution is a set of tours: each tour starts and ends at the depot after visiting a set of clients in a way that the sum of the clients’ demands on a tour (the tour load) does not violate the capacity constraint. Each client must be visited exactly once. The objective is to minimize the total traveling cost. A special version is when each client demand is unit (i.e. dv = 1 for a client v). In this case, the capacity restriction is given
Data Loading...
