Fast heuristics for a combined production planning and vehicle routing problem

Abstract : This paper studies a problem of production and distribution of one product on a multi-period horizon. The value of co-ordinating production and distribution planning is investigated. The particular scenario addressed here concerns a plant that manufactures one product that can be stored at the plant or shipped to customers who can also store it. The product is distributed by a limited fleet of vehicles to the customers whose the demands are known for each period of the planning horizon. The objective is to determine, for each period, the amount produced and the delivery trips, in order to minimise the total cost of production and distribution over the whole horizon. Two greedy heuristics followed by two local search procedures are proposed for this difficult problem. The first heuristic or uncoupled approach computes in a classical way a production plan and then a distribution plan. The second one or coupled approach determines the two plans simultaneously. The one product hypothesis is not restricted since our heuristics can be extended to cases of several products if these products can be mixed in the same vehicles without creating resource conflicts in production. These heuristics are tested on randomly generated instances with up to 200 customers and 20 periods: they are all very fast and significant savings are obtained by the coupled approach.