Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees | Zendy

Kemal Altınkemer | Zendy; Bezalel Gavish | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees

Author(s) -

Kemal Altınkemer,

Bezalel Gavish

Publication year - 1990

Publication title -

transportation science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.965

H-Index - 115

eISSN - 1526-5447

pISSN - 0041-1655

DOI - 10.1287/trsc.24.4.294

Subject(s) - travelling salesman problem , heuristics , mathematical optimization , constant (computer programming) , iterated function , computer science , mathematics , mathematical analysis , programming language

In this paper Q Iterated Optimal Tour Partitioning, and Best Optimal Tour Partitioning algorithms are studied and analyzed for their worst case error. Both algorithms are based on partitioning an optimal traveling salesman tour in order to generate a feasible solution to the unit weight delivery problem. They have a worst case error bound of 2-1/Q where Q is the maximal number of customers a vehicle could visit and N is the total number of customers. Similar worst case error bounds are shown when the algorithms are applied to an α-optimal traveling salesman tour.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research