The Jeep Problem: A Flexible MIP Formulation

Abstract

This article deals with the Jeep Problem (also known as Desert Crossing Problem), which reads as follows: An unlimited supply of fuel is available at one edge of a desert, but there is no source on the desert itself. A vehicle can carry enough fuel to go a certain distance, and it can built up its own refuelling stations. What is the minimum amount of fuel the vehicle will require in order to cross the desert? Under these mild conditions this question is answered since the 1940s. But what is the answer if the caches are restricted to certain areas or if the fuel consumption does not depend linearly on the distance travelled? To answer these and similar questions we develop and solve a flexible mixed-integer programming (MIP) model for the classical problem and enhance it with new further aspects of practical relevance.