Advertisement
Published in:
20-05-2019
Improved algorithms for single vehicle scheduling on tree/cycle networks
Published in: Journal of Combinatorial Optimization | Issue 3/2021
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The single vehicle scheduling problems based on tree/cycle networks are studied in this paper. Each customer, assumed as a vertex on the given network, has a release time and a service time requirement. The single vehicle starts from the depot and aims to serve all the customers. The objective of the problem is to find the optimal routing schedule so as to minimize the makespan. We provide a \(\frac{16}{9}\)-approximation algorithm and a \(\frac{48}{25}\)-approximation algorithm for the tour-version and path-version of single vehicle scheduling problem on a tree, respectively. For the tour-version and path-version of single vehicle scheduling problem on a cycle, we present a \(\frac{5}{3}\)-approximation algorithm and a \(\frac{29}{17}\)-approximation algorithm, respectively.