Solving the mTSP for fresh food delivery

Abstract

A starting company intends to deliver fresh baby food at home addresses in the area of Zwolle, the Netherlands. The limited time windows of delivery encourage the notion of dividing the addresses over several shifts. Dividing optimal routes over these shifts is shown to be an instance of the multiple traveling salesman problem (mTSP). Three problems are posed, all relating in one way or another to solving the mTSP: 1. Solve the mTSP for the specified delivery area; 2. Find an efficient method for solving an mTSP in which certain nodes may only be visited by certain salesmen; 3. Estimate the largest amount of customers that may be serviced per four hour shift. A number of methods to solve the mTSP are presented: namely branch and bound, greedy search, simulated annealing and neural networks. The first three of these methods are also modified to handle customer availabilities on specific shifts. The methods are tested and compared within the context of the three different problems. The results of these tests are discussed and solutions to the three problems are suggested.