Open vehicle routing problem with multi-period and postponable demands

In the Open Vehicle Routing Problem (OVRP) which is a variant of classical vehicle routing problem, the vehicles do not have to return to the depot after servicing the customers. In OVRP, the aim is to minimize total delivery costs while all customer demands are satisfied under vehicle capacity constraints. In the scope of this thesis, the OVRP with multi-period and postponed demands is considered and two different mathematical models are established for the problem. In this problem, instead of routing the vehicles statically for once, it is possible to postpone and merge the demands which arrive at different days in a planning horizon. Merging the demands can cause a rise in holding costs while providing a reduction in transportation costs. The established mathematical models aim to minimize total traveling and holding costs by regarding this trade-off. Unlike multi-period vehicle routing problems in the literature, in this study, it is considered for the first time that customers can have demand more than once in a planning horizon. The constructed mathematical models include nonlinear functions. Because finding an optimal solution with nonlinear models is difficult and time consuming, a linearization method is applied to the models. Mathematical models are solved for real-life examples composed of 5, 7 and 9 customers. Due to the NP-hard structure of the problem, small-size samples are selected. Keywords: Open vehicle routing problem, Multi-period vehicle routing problem, Postponable demands