Approximation Algorithms for the Capacitated Vehicle Routing Problem

Speaker:

Jingyang Zhao (Ph.D. student in University of Electronic Science and Technology of China)

Time:

16:20-17:20 (Time in Beijing)
21:20-22:20 (Time in Auckland)
April 15, 2022 (Friday)

Venue:

B1-518B, Research Building 4

Abstract:

In the Capacitated Vehicle Routing Problem (CVRP), we are given an undirected complete graph $G=(V\cup{v_0}, E)$ with metric nonnegative edge weights, where there are $n$ nodes in $V$ representing $n$ customers, each customer $v_i$ with a demand $q_i\in\mathbb{N}<em>{\geq 1}$ and a vehicle located at the depot $v_0$ with a capacity of $k\in\mathbb{N}</em>{\geq 1}$ . We wish to find a set of tours to cover the demand of every customer with a minimized total weight of edges such that each tour begins and ends at the depot and the sum deliveries for customers in each tour is at most $k$ .

This problem has many results in different areas. I mainly consider the results of approximation algorithms in the metric case. In this talk, I will first summarize some current results and then I will introduce some new results.