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

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

Subrata Mitra (Department of Operations Management, Indian Institute of Management-Calcutta, Joka, Calcutta, India)
Copyright: © 2013 |Pages: 17
DOI: 10.4018/jal.2013040101
OnDemand PDF Download:
$37.50

Abstract

Dynamic vehicle routing problems with backhauling (VRPB), although important, have attracted little attention in the literature. Dynamic VRPB is more complex than dynamic vehicle routing problems (VRP) without backhauling, and since VRP without backhauling is a special case of VRPB, models and algorithms for dynamic VRPB can easily be adapted for dynamic VRP. In this paper, the author compared between static and dynamic policies for solving VRPB with dynamic occurrences of customer delivery and pickup demands. They developed heuristic algorithms for medium-sized problems under static and dynamic policies. Although dynamic policies are always at least as good as static policies, the author observed from numerical experimentations that static policies perform relatively well for low degrees of dynamism (dod). On the other hand, dynamic policies are expected to perform significantly better than static policies for high dod and early availabilities of dynamic customer delivery and pickup demand information. The author concludes the paper by providing directions for future research on dynamic VRPB.
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 7: 2 Issues (2017): 1 Released, 1 Forthcoming
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing