A Dynamic Messenger Problem

Abstract

Messenger services provide customers to deliver their package from a specific origin to a specific destination. Real situations require the fast messenger’s reaction to the on-line customer’s request. While it is not possible to change the planned route in static distribution problems, a dynamic version enables a dispatcher the integration of a new request to existing route for optimization. The mathematical models proposed in the paper are based on the Miller-Tucker-Zemlin’s formulation of Traveling Salesman Problem. Because of NP hardness of the problem it is impossible for most real problems to find the optimal solution in acceptable time. Heuristic algorithms represent the important alternative to solving real dynamic problems. Basic formulation of the messenger problem can be extended to problems with time windows. Limited capacity of the vehicle and multiple vehicles can be also considered.