This paper describes a decision support system that has been developed to manage petroleum deliveries from a bulk terminal to petrol stations using a fleet of petrol tanker trucks. The problem is defined as a petrol station replenishment problem with customer demands determined using a prediction algorithms based on time series of daily sales. The DSS employs a user-defined road network as the underlying transport to meet governmental hazardous goods transport regulations. The system was implemented and has been in operation for over 18 months. Delivery costs per litre delivered have decreased 15% in comparison with those of previous years.
In this paper we consider the problem of vehicle assignment in heterogeneous fleet site-dependent Vehicle Routing Problems (VRP) with split deliveries. In such VRP problems vehicles can have different capacities, fixed and travel costs, and site-dependency constraints limit for every customer a set of vehicles, which can serve it. The Vehicle Assignment Problem (VAP) arises in heuristic and exact algorithms, when vehicles are assigned to all customers or one customer is added to the current vehicle route. The VAP objective is to minimize the total assignment cost while the cost of assigning a vehicle to a customer is computed in some heuristic way. Without split deliveries, when a delivery to a customer cannot be split between two vehicles, the VAP problem is modeled in literature as the Generalized Assignment Problem. We demonstrate that allowing split deliveries reduces the VAP to the Hitchcock Transportation Problem, which can be efficiently solved with Transportation Simplex Methods. We also consider a special case, which is not rare in practice, when all customers are partitioned into classes, where customers have the same set of vehicles able to serve them, and the vehicle sets for these classes form a sequence of nested sets. We show that in this case if the cost per demand unit of assigning a vehicle to a customer depends only on the vehicle, then the VAP problem can be solved by a linear algorithm.