Abstract
Vehicle routing problems (VRPs) have been well-studied since they were first introduced in combinatorial optimization theory some 55 years ago, both due to their scientific interest and a wide range of applications. For capacitated routing problems, the goal is to determine a set of routes for a fleet of capacitated vehicles that service customers in an optimal way. The customers are located on elements of a graph that defines the possible paths and associated travel costs.
VRPs are often divided into two classes according to the type of components of the graph that require service. Problems where all customers are located in points, i.e. on a subset of the nodes in a graph representation, are categorized as node routing problems. The prime example is the classical Capacitated Vehicle Routing Problem (CVRP) first defined by Dantzig and Ramser (1959) [5]. In routing applications such as street sweeping, gritting, and snow clearance, a street segment is the basic entity where demand for service is located. In a natural VRP representation, all customers are located on edges or arcs in the graph. Such VRPs are called arc routing problems. The arc routing equivalent of the CVRP is the Capacitated Arc Routing Problem (CARP) that was introduced by Golden and Wong (1981) [7].
The node vs. arc routing categorization nearly dichotomizes the VRP literature. Although there are many applications where customers are naturally located both in points and on street segments, the literature merely contains a dozen or so papers on capacitated routing problems with service both on nodes and links. In contrast, there is substantial literature on the node and link generalization of the Travelling Salesman Problem, i.e., the General Routing Problem (GRP) introduced by Orloff (1974) [15], and its uncapacitated extensions. To our knowledge, Pandi and Muralidharan (1995) [16] were the first to introduce a capacitated general routing problem with multiple vehicles. The authors studied such a GRP generalization based on a mixed graph, with a heterogeneous fixed fleet, and a maximum route duration constraint. They investigated a route-first-cluster-second heuristic on test instances inspired from curb-side waste collection in residential areas, and on random instances from the Capacitated Chinese Postman Problem. The homogeneous fleet version of this problem without the route duration constraint has later been known as the Mixed Capacitated General Routing Problem (MCGRP).
Heuristic approximation methods for the MCGRP have been studied by Gutiérrez et al. (2002) [8], Prins & Bouchenoua (2005) [19], Kokubugata et al. (2007) [13], Hasle et al. (2012) [9], and Dell'Amico et al. (2014) [6]. Bach et al. (2013) [1] designed the first combinatorial lower bound procedure for the MCGRP. Bosco et al. (2013) [4] developed the first integer programming
formulation and proposed the first exact method for the MCGRP, based on Branch & Cut. Bode, Irnich, Laganà, and Vocaturo (2014) [3] present a new mathematical formulation for the MCGRP and propose a two-phase Branch & Cut algorithm. Bach, Lysgaard and Wøhlk (2014) [2] propose a Branch & Cut & Price for the problem.
Although it is certainly an important aspect of many real-life VRPs, route balancing has drawn surprisingly little attention in the literature. Jozefowiez et al. (2008) [11] provide a survey of multi-objective VRPs with some 70 references, but only a handful of papers study VRP with route balancing. A VRP solution, however close to optimal regarding travel cost, will often be considered useless in practice if the variation in duration, cost, or workload between routes is too large.
We investigate the bi-criteria MCGRP with Route Balancing (MCGRP-RB), where total duration is one criterion, and route balance is the second. We minimize route imbalance by minimizing the difference in duration of the longest and the shortest route. Our approach is true bi-criteria optimization, i.e. our goal is to
VRPs are often divided into two classes according to the type of components of the graph that require service. Problems where all customers are located in points, i.e. on a subset of the nodes in a graph representation, are categorized as node routing problems. The prime example is the classical Capacitated Vehicle Routing Problem (CVRP) first defined by Dantzig and Ramser (1959) [5]. In routing applications such as street sweeping, gritting, and snow clearance, a street segment is the basic entity where demand for service is located. In a natural VRP representation, all customers are located on edges or arcs in the graph. Such VRPs are called arc routing problems. The arc routing equivalent of the CVRP is the Capacitated Arc Routing Problem (CARP) that was introduced by Golden and Wong (1981) [7].
The node vs. arc routing categorization nearly dichotomizes the VRP literature. Although there are many applications where customers are naturally located both in points and on street segments, the literature merely contains a dozen or so papers on capacitated routing problems with service both on nodes and links. In contrast, there is substantial literature on the node and link generalization of the Travelling Salesman Problem, i.e., the General Routing Problem (GRP) introduced by Orloff (1974) [15], and its uncapacitated extensions. To our knowledge, Pandi and Muralidharan (1995) [16] were the first to introduce a capacitated general routing problem with multiple vehicles. The authors studied such a GRP generalization based on a mixed graph, with a heterogeneous fixed fleet, and a maximum route duration constraint. They investigated a route-first-cluster-second heuristic on test instances inspired from curb-side waste collection in residential areas, and on random instances from the Capacitated Chinese Postman Problem. The homogeneous fleet version of this problem without the route duration constraint has later been known as the Mixed Capacitated General Routing Problem (MCGRP).
Heuristic approximation methods for the MCGRP have been studied by Gutiérrez et al. (2002) [8], Prins & Bouchenoua (2005) [19], Kokubugata et al. (2007) [13], Hasle et al. (2012) [9], and Dell'Amico et al. (2014) [6]. Bach et al. (2013) [1] designed the first combinatorial lower bound procedure for the MCGRP. Bosco et al. (2013) [4] developed the first integer programming
formulation and proposed the first exact method for the MCGRP, based on Branch & Cut. Bode, Irnich, Laganà, and Vocaturo (2014) [3] present a new mathematical formulation for the MCGRP and propose a two-phase Branch & Cut algorithm. Bach, Lysgaard and Wøhlk (2014) [2] propose a Branch & Cut & Price for the problem.
Although it is certainly an important aspect of many real-life VRPs, route balancing has drawn surprisingly little attention in the literature. Jozefowiez et al. (2008) [11] provide a survey of multi-objective VRPs with some 70 references, but only a handful of papers study VRP with route balancing. A VRP solution, however close to optimal regarding travel cost, will often be considered useless in practice if the variation in duration, cost, or workload between routes is too large.
We investigate the bi-criteria MCGRP with Route Balancing (MCGRP-RB), where total duration is one criterion, and route balance is the second. We minimize route imbalance by minimizing the difference in duration of the longest and the shortest route. Our approach is true bi-criteria optimization, i.e. our goal is to