Considerations on Set Partitioning and Set Covering Models for Solving the 2E-CVRP in City Logistics: Column Generation and Solution Probleming Analysis

Considerations on Set Partitioning and Set Covering Models for Solving the 2E-CVRP in City Logistics: Column Generation and Solution Probleming Analysis

Copyright: © 2019 |Pages: 29
DOI: 10.4018/978-1-5225-8292-2.ch004

Abstract

This chapter proposes a position viewpoint, discussion, and analysis of various aspects of solving 2E-CVRP problems via exact methods, more precisely the use of set partitioning formulations (and consequently set covering ones), as well as column generation to produce bounds and feed branch-and-prize approaches. After an overview of the main exact methods used to solve 2E-CVRP approaches, the author defines the main notions and variables to model the problem via set covering and set partitioning models. Then the paper presents two methods to generate bounds via column generation: the first is a decomposition approach in which first-echelon and second-echelon routes are generated separately, without any relation, and the second generate sets of linked first-echelon and second-echelon routes. The main implications and considerations of those methods are addressed. Finally, main issues regarding the suitability of exact methods for vehicle routing in city logistics are presented.
Chapter Preview
Top

Introduction

Two-echelon vehicle routing is a challenging problem that has been studied by various researchers, mainly related to city logistics. Previous chapter presented the main issues on the problem as well as compared two formulations and briefly presented the main literature concerning heuristics (which did not evolve, for the basic version of the problem, in a strong way since 20121). However, to validate and state on the suitability of heuristic method, it is important to have a basis to compare the results of that method, and this is mainly done defining standard instances and finding exact optima or near-optimal solutions (Toth & Vigo, 2002). In that context, exact methods are less developed than heuristics, and we find them mainly for the basic variant of the problem. Although the three main categories of exact methods usually deployed for VRP are found for 2E-CVRP (Branch-and-Bound, Branch-and-Cut and Branch-and-Price), it is the first of them, i.e. Branch-and-Bound, which seems to be the most performing, arriving to solve optimally almost all instances up to 50 customers of those initially proposed by Gonzalez-Feliu et al. (2007) for this problem (the best algorithm found for those instances is that of Baldacci et al., 2013). Moreover, upper and lower bounds are found for instances up to 200 customers on a similar problem, the 2E-LRP (Contardo et al., 2013). Nevertheless, the first appointed method was Branch-and-Price and Column generation, but that approach resulted not really adapted to the problem because of the nature of the problem. Although initially appointed in a previous research (Gonzalez-Feliu, 2008), results were difficult to be published since they did not follow the classical logic of operations research. Anyway, they are interesting if related to the physical systems, to city logistics real problems and more generally if they are analyzed in a solution probleming vision (Ackoff, 1977), which is minority in operations research but starts to be unified and consensually accepted (Kirby, 2003; Gonzalez-Feliu, 2013b).

The solution probleming approach is proposed by Ackoff (1977) to deal with the lack of representation and suitability, in terms of proximity to reality and real applications, of operations research (OR) dominant, math-based, formalistic approaches. Indeed, according to the author, the optimal solution of an optimization model cannot be really optimal for a given problem unless the model is a suitable2 representation of that problem. However, classical OR approaches focus on the solving method and the search of an “optimal solution” for a given model, but not on examining if the model is a correct of at least suitable representation of a reality. Moreover, and if we take into account that every model is a representation of the reality (and not the reality itself), as seen by the modeler (Gonzalez-Feliu, 2018), it is important to relate that model to the reality it aims to represent, to examine its suitability (Gonzalez-Feliu & Sanchez-Diaz, 2017). For that, and following the principles of Ackoff (1977), we can state that optimization follows what we will call the “cycle of optimization”, defined as a combination of three main phases:

Complete Chapter List

Search this Book:
Reset