A heuristic algorithm for the free newspaper delivery problem

This paper addresses th problem of finding an effective distribution plan to deliver free newspapers from a production plant to subway, bus, or tram stations. The overall goal is to combine two factors: fist the free newspaper producing company wants to minimize the numver of vehicle trips needed to distribute all newspapers produced at the production plant. Second, the company is interested in minimizing the time needed to consume all newspapers, i.e., the time needed to get all the newspapers taken by the final readers. The resulting routing problem combines aspects of the vehicle routing problem with time windows, the inventory routing problem, and additional constraints related to the production schedule. We propose a formulation and different heuristic approaches, as well as a hybrid method. Computational tests with real world data show that the hybrid method ist the best in various problem settings.