An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
From MaRDI portal
Publication:1884949
DOI10.1016/j.tcs.2003.09.010zbMath1067.90143MaRDI QIDQ1884949
Hiroshi Nagamochi, Yoshiyuki Karuno
Publication date: 27 October 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2003.09.010
Dynamic programming; Discrete optimization; Polynomial time approximation scheme; Vehicle scheduling
90B35: Deterministic scheduling theory in operations research
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
90C39: Dynamic programming
Related Items
Approximation schemes for Euclidean vehicle routing problems with time windows, Routing open shop and flow shop scheduling problems, Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle, Set covering in fuel-considered vehicle routing problems, Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints, Minmax subtree cover problem on cacti, A Quasi-polynomial Time Approximation Scheme for Euclidean CVRPTW, Single-vehicle scheduling problems with release and service times on a line
Cites Work
- A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times
- Single-vehicle scheduling with time window constraints
- Vehicle scheduling on a tree with release and handling times
- \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
- A polynomial approximation scheme for problem \(F2/r_ j/C_{\text{max}}\)
- 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
- A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
- Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
- Routing and Scheduling on a Shoreline with Release Times
- Special cases of traveling salesman and repairman problems with time windows
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- A Polynomial Approximation Scheme for a Constrained Flow-Shop Scheduling Problem
- Technical Note—Routing and Location-Routing p-Delivery Men Problems on a Path
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- Complexity Of The Single Vehicle Scheduling Problem On Graphs
- Sales‐delivery man problems on treelike networks
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
