Approximation algorithms for solving the heterogeneous Chinese postman problem

DOI10.1007/S10878-022-00931-5MaRDI QIDQ2106868zbMATH OpenOpenAlexFDO

Authors Jianping Li, Pengxiang Pan, Junran Lichen, Lijian Cai, Wencheng Wang, Suding Liu

Publication date 29 November 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-022-00931-5

zbMATH Keywords

combinatorial optimizationapproximation algorithmsheterogeneous Chinese postman toursnonuniform speeds

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• An approximation algorithm for solving the heterogeneous Chinese postman problem
• scientific article; zbMATH DE number 1947382
• Capacitated vehicle routing with nonuniform speeds
• scientific article; zbMATH DE number 1187150
• Approximation algorithms for some min-max postmen cover problems

Cites work

• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• A (slightly) improved approximation algorithm for metric TSP
• A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem
• An approximation algorithm for solving the heterogeneous Chinese postman problem
• Capacitated vehicle routing with nonuniform speeds
• Combinatorial optimization. Theory and algorithms.
• Matching, Euler tours and the Chinese postman
• Min-Max Tours and Paths for Task Allocation to Heterogeneous Agents
• The vehicle routing problem. Latest advances and new challenges.
• Vehicle Routing
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(9)

• Approximating the length of Chinese postman tours
• The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game
• An approximation algorithm for solving the heterogeneous Chinese postman problem
• Capacitated vehicle routing with non-uniform speeds
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• Approximate solutions for the maximum benefit chinese postman problem
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• An improved heuristic algorithm for the maximum benefit Chinese postman problem

Describes a project that uses

Uses Software

• VRP

This page was built for publication: Approximation algorithms for solving the heterogeneous Chinese postman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2106868)