Algorithmic approaches to solving multi-period sales force and delivery vehicle master routing problems

Abstract

Many companies are confronted with the problem of creating xed master routes for a period of more than a day either for geographically dispersed sales representatives or for eets of delivery vehicles which operate from a single depot. This involves the assignment of the company's customers to the sales reps/vehicles as well as visit pro les. For the problems de ned herein, these allocations of customers to a service group must remain xed for the duration of the planning period. A pro le represents a valid combination of visit days for a customer as well as a proportion of distributable workload (time for sales reps or mass for delivery vehicles) for each visit. For the sales rep problem, there is the option to solve for the optimal number of salesmen and their home locations if they are not known. Also, routes for the salesmen may include a new feature, sleep-outs, which are governed by rules indicating possible combinations of nights spent away from home as well as sleep-out locations. These combinatorial optimization problems are solved using exact and heuristic branch-and-bound algorithms which also assists in de ning the problem complexity. A genetic algorithm hybridised with problem speci c heuristics (i.e. a memetic algorithm) is also applied to problems which cannot be solved exactly in a reasonable amount of time. This evolutionary programming metaheuristic technique uses natural multi- level data structures and problem-sensitive genetic operators.