Approximation Algorithms for the Capacitated Vehicle Routing Problem
- Speaker
- Jingyang Zhao
- Affiliation
- Ph.D. student in University of Electronic Science and Technology of China
- Date
- Time
- – Asia/Shanghai
- 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}_{\geq 1}$ and a vehicle located at the depot $v_0$ with a capacity of $k\in\mathbb{N}_{\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.
Schedule
- 16:20-17:20 (Time in Beijing)
- 21:20-22:20 (Time in Auckland)
- April 15, 2022 (Friday)