Solving the Mixed Backhauling Vehicle Routing: Problem with Ants

Solving the Mixed Backhauling Vehicle Routing: Problem with Ants

Niaz A. Wassan (Center for Logistics and Heuristics Optimization, Kent Business School, University of Kent, Canterbury, Kent, UK), Said Salhi (Center for Logistics and Heuristics Optimization, Kent Business School, University of Kent, Canterbury, Kent, UK), Gábor Nagy (Center for Logistics and Heuristics Optimization, Kent Business School, University of Kent, Canterbury, Kent, UK), Naveed Wassan (Center for Logistics and Heuristics Optimization, Kent Business School, University of Kent, Canterbury, Kent, UK) and Anne C. Wade (BAE Systems, Insyte, Filton, UK)
Copyright: © 2013 |Pages: 16
DOI: 10.4018/ijeoe.2013040105
OnDemand PDF Download:
$37.50

Abstract

The mixed vehicle routing problem with backhauls is investigated using ant system heuristic. This distribution problem seems to suffer from a lack of published work even though it has immense practical applicability especially within logistic systems. Some enhancements to the basic ant system algorithm are embedded into the search. In particular a focus is on the choice in the placement of ants, the use of site-dependent candidate list, the introduction of a look ahead-based visibility, and appropriate strategies for updating local and global trails. Encouraging computational results are reported when tested on benchmark data sets.
Article Preview

1. Introduction

The vehicle routing problem with backhauls (VRPB) is an extension to the vehicle routing problem (VRP) where two different types of customers exist. The first type consists of linehaul customers, also known as delivery customers, who require a given quantity of product to be delivered. The second type are the backhaul customers, also known as pickup customers, who require a quantity of goods to be picked up and sent back to the depot. Hence, the VRPP is also known as the vehicle routing problem with pickups and deliveries. The goods are transported to or from a single depot by a fleet of homogeneous vehicles. The objective is to find a set of routes with the least cost where all customer demands are satisfied, each customer is visited exactly once, all routes begin and end at the depot, and finally the load on the vehicle at any arc along the route does not exceed the vehicle capacity.

The VRPB models in the literature either restrict backhauls to be visited once all linehauls have been served, the classical VRPB, or allow a mix of linehaul and backhaul customers along the routes, the mixed VRPB. The latter problem is also known as the vehicle routing problem with mixed pickups and deliveries, and is closely related to the problem of vehicle routing with simultaneous pickups and deliveries, where each customer can have both a pickup and a delivery load. The focus of our paper is on the mixed VRPB. In the classical VRPB it is only necessary to check that the total linehaul load and the total backhaul load do not separately exceed the total vehicle capacity. In the mixed VRPB it is necessary to check that the vehicle capacity is not exceeded at any arc along the route, since in this problem the vehicle load can either decrease or increase at each customer site depending on whether the customer is a linehaul or a backhaul. The classical case is often solved by matching two partial routes: one containing linehauls and the other backhauls. The mixed case is typically solved by inserting backhauls into linehaul routes. The mixed classical VRPB has not received as much attention in the literature as its counterpart the classical VRPB. This has some practical justification given that many vehicles are rear-loaded and that linehaul customers usually prefer early deliveries while backhaul ones may not object to late deliveries. However, the improved design of vehicles, in particular vehicles that permit side loading, mean that mixed routes are now a much more practical option and therefore worth investigating. Such a motivation is obviously also of interest to the case of simultaneous VRPB. In other words, in the mixed VRPB we are allowed to mix linehaul and backhaul customers within a given route as long as feasibility, in terms of vehicle capacity and time restriction, are not violated. Though such flexibility may provide cheaper scheduling costs, it adds extra difficulties in the checking of the vehicle capacity as the load will now fluctuate along the route.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 6: 4 Issues (2017)
Volume 5: 4 Issues (2016)
Volume 4: 4 Issues (2015)
Volume 3: 4 Issues (2014)
Volume 2: 4 Issues (2013)
Volume 1: 4 Issues (2012)
View Complete Journal Contents Listing