Comparing Static and Dynamic Policies for Vehicle Routing Problems with Backhauling and Dynamic Customer Demands

Introduction

In the traditional vehicle routing problem (VRP) without backhauling, a depot has to serve the linehaul demands of a set of customers with a fleet of vehicles. The objective is to determine the vehicle routes in order to minimize the total travelling time/cost of the vehicles. There is a vast literature on the VRP, which describes the problem as NP-Hard. A number of variants of the basic VRP exist such as multiple depots, multiple time periods, time windows, service times, maximum route time limitations on vehicles and so on. An even more difficult problem is the vehicle routing problem with backhauling (VRPB) where a customer may have both linehaul and backhaul demands (In case a customer has either linehaul or backhaul demands, this can be achieved by equating backhaul or linehaul demands, respectively, of the customer to zero). It is intuitive that VRP is a special case of VRPB where the backhaul demands of customers are zero. Therefore, the problem considered in this paper is more general in nature. Since both VRP and VRPB are NP-Hard, the solution approach in the literature so far has been the development of exact or mixed integer linear programming (MILP) formulations for solving small-sized problems and approximate or heuristic algorithms for solving medium to large-sized problems. For the different variants of VRP/VRPB and their solution methodologies, readers are referred to Goetschalckx and Jacobs-Blecha (1989), Laporte et al. (2000), Ropke and Pisinger (2006) and Mitra (2008). Recent references on VRPB include Paraphantakul (2011), Zachariadis and Kiranoudis (2011, 2012), Tasan and Gen (2012), Goksal et al. (2012), Karaoglan et al. (2012), Tarantilis et al. (2012) and Wassan et al. (2012). Also, see Huang and Xu (2013) for new methodologies (such as auctions) to address VRPB.