Solving the mTSP for fresh food delivery

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.

Subject

mTSP
multiple
traveling
salesman
problem
branch and bound
greedy search
simulated annealing
neural networks

To reference this document use:

http://resolver.tudelft.nl/uuid:8af405cc-bdd1-46c0-a790-a66471eadb3f

Coordinates

52.5, 6.0833333

Part of collection

Student theses

Document type

bachelor thesis

Rights

Files

PDF

aangepast.pdf

1.44 MB

Close viewer