Simple heuristics for the multi-period fleet size and mix vehicle routing problem

ABSTRACT

Most of the research on vehicle routing problems has focused on the operational or the tactical level. However, any decision made on a strategic level will affect the lower level decisions. One type of strategic decision that has been considered in the literature is to compose an appropriate fleet of different vehicles to perform transportation tasks, which yields the fleet size and mix vehicle routing problem (FSMVRP). This work defines a new variant of the FSMVRP where the customer demands may vary over a set of periods, for example by having different demands on each day of the week. The objective is to find the best fleet composition that can be used to repeatedly fulfil the customer demands, as well as the best routing with that fleet for each of the different periods in the planning horizon. Simple heuristics incorporating a tabu search are implemented to find the fleet composition. Computational results are reported on instances created from a set of standard FSMVRP test instances.

KEYWORDS:

• Tabu search
• shrinking and expanding heuristic
• fixed fleet

Acknowledgements

We thank the late professor Arne Løkketangen for providing the idea for the work presented in the paper. Two anonymous referees are thanked for their valuable inputs that helped to improve the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.