Competitive analysis of a dispatch policy for a dynamic multi-period routing problem

Competitive analysis of a dispatch policy for a dynamic multi-period routing problem

0.00 Avg rating0 Votes
Article ID: iaor20083828
Country: Netherlands
Volume: 35
Issue: 6
Start Page Number: 713
End Page Number: 721
Publication Date: Nov 2007
Journal: Operations Research Letters
Authors: , ,
Abstract:

We analyze an on-line algorithm (dispatch policy) for a dynamic multi-period routing problem. The objective is to minimize the total cost over all periods. We show that the competitive ratio of this policy for instances with customers located on the non-negative real line is 3/2.

Reviews

Required fields are marked *. Your email address will not be published.