9 papers
Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
Jingyang Zhao, Mingyu Xiao
The capacitated vehicle routing problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. In this problem, we are given a depot and a set of cus…
Improved Approximations for Dial-a-Ride Problems
Jingyang Zhao, Mingyu Xiao
The multi-vehicle dial-a-ride problem (mDaRP) is a fundamental vehicle routing problem with pickups and deliveries, widely applicable in ride-sharing, economics, and transportation…
Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
Jingyang Zhao, Yonghang Su, Mingyu Xiao
The Multiple-Depot Split Delivery Vehicle Routing Problem (MD-SDVRP) is a challenging problem with broad applications in logistics. The goal is to serve customers' demand using a f…
An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
Jingyang Zhao, Mingyu Xiao
Given a complete graph with vertices and non-negative edge weights, where is divisible by 3, the maximum weight 3-path packing problem is to find a set of vertex-disj…
An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
Jingyang Zhao, Mingyu Xiao
The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is an important arc routing problem in Operations Research, which generalizes the famous Capacita…
Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
Jingyang Zhao, Mingyu Xiao
In the Cumulative Vehicle Routing Problem (Cu-VRP), we need to find a feasible itinerary for a capacitated vehicle located at the depot to satisfy customers' demand, as in the well…