New mathematical models of the generalized vehicle routing problem and extensions

by

Petrică C. Pop

Imdat Kara

Andrei Horvat-Marc

Applied Mathematical Modelling, Volume 36, Issue 1, January 2012, Pages 97–107 DOI

Matching entries: 0
settings...
2017
1Defryn C and Sorensen K (2017), A fast two-level variable neighborhood search for the clustered vehicle routing problem, COMPUTERS & OPERATIONS RESEARCH., JUL, 2017. Vol. 83, pp. 78-94.

[BibTeX] [DOI]
BibTeX: 
@article{ISI:000399511200007,
  author = {Defryn, Christof and Sorensen, Kenneth},
  title = {A fast two-level variable neighborhood search for the clustered vehicle routing problem},
  journal = {COMPUTERS & OPERATIONS RESEARCH},
  year = {2017},
  volume = {83},
  pages = {78-94},
  doi = {https://doi.org/10.1016/j.cor.2017.02.007}
}
2Ju C, Zhou G and Chen T (2017), Disruption management for vehicle routing problem with time-window changes, INTERNATIONAL JOURNAL OF SHIPPING AND TRANSPORT LOGISTICS. Vol. 9(1), pp. 4-28.

[Abstract] [BibTeX] [DOI]
Abstract: In this paper, based on disruption management method, logistics
distribution vehicle routing problem with soft time-window changes
considering disruptions is explored. Firstly, by analysing the
customers' requirements characteristics and the disadvantage of rigid
time window, the soft time-window constraint is considered and the
corresponding mathematical model is also setup. Secondly, according to
the disruption management method, disruption factors including
customers' satisfaction, path offsets, total distribution cost for
time-window changes are analysed and the method of disruptions measure
which considers synthetically the customers, logistics service provider
and driver is proposed. A disruption recovery model for the problems is
put forward based on the reposition strategy. Thirdly, in order to solve
this multi-objective model, an artificial bee colony (ABC) which can
optimise this NP-hard problem is developed. Finally, a numerical
simulation experiment is used to verify this model and algorithm. The
results illustrate the effectiveness of ABC in solving this problem.
BibTeX: 
@article{ISI:000397066000001,
  author = {Ju, Chunhua and Zhou, Guanglan and Chen, Tinggui},
  title = {Disruption management for vehicle routing problem with time-window changes},
  journal = {INTERNATIONAL JOURNAL OF SHIPPING AND TRANSPORT LOGISTICS},
  year = {2017},
  volume = {9},
  number = {1},
  pages = {4-28},
  doi = {{10.1504/IJSTL.2017.10000921}}
}
2016
3Kuo RJ, Wibowo BS and Zulvia FE (2016), Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time, APPLIED MATHEMATICAL MODELLING., DEC, 2016. Vol. 40(23-24), pp. 9990-10001.

[Abstract] [BibTeX] [DOI]
Abstract: Service management has been an important issue for many companies,
especially for service-based companies. This paper studies a routing
problem that is usually faced by on site service companies. This type of
company continuously receives orders during its working hours. In order
to maximize the number of customers served and minimize the customer
waiting time, the service team is responsible for determining which
orders should be served during the ongoing working period and which
orders should be served in the following working period. This paper
represents this problem as a dynamic vehicle routing problem (DVRP). The
proposed DVRP model also considers the uncertain service time using
fuzzy theory. Furthermore, an algorithm using an improved fuzzy ant
colony system (ACS) is proposed in order to solve the proposed model.
The proposed algorithm embeds a cluster insertion algorithm into the ACS
algorithm. The proposed algorithm is validated using some benchmark
datasets. The results show that the proposed algorithm performs better
than the previous fuzzy-ACS algorithm without cluster insertion
algorithm. In addition, further sensitivity analysis is also presented
to derive more information about the model and the proposed algorithm
for application to real-world problems. (C) 2016 Elsevier Inc. All
rights reserved.
BibTeX: 
@article{ISI:000393539100020,
  author = {Kuo, R. J. and Wibowo, B. S. and Zulvia, F. E.},
  title = {Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time},
  journal = {APPLIED MATHEMATICAL MODELLING},
  year = {2016},
  volume = {40},
  number = {23-24},
  pages = {9990-10001},
  doi = {10.1016/j.apm.2016.06.025}
}
4Li H, Lv T and Lu Y (2016), The Combination Truck Routing Problem: A Survey, In GREEN INTELLIGENT TRANSPORTATION SYSTEM AND SAFETY. Vol. 138, pp. 639-648.

[Abstract] [BibTeX] [DOI]
Abstract: The combination-vehicle attributes of vehicle routing problems are
additional characteristics that aim to consider more effectively the
specificities of real logistics applications. Because various
combination truck situations exist, the combination truck routing
problem (CTRP) is supported by well-developed literature, especially
with respect to the truck and trailer routing problem (TTRP), the
rollon-rolloff vehicle routing problem (RRVRP), the tractor and
semitrailer routing problem (TSRP), and a variety of heuristics. This
article first reviews the three primary forms of the CTRP, providing a
survey of problem foundations and heuristics for the TTRP, the RRVRP and
the TSRP. Next, this report takes a closer look at comparing the three
forms of the CTRP. The TTRP aims to efficiently apply trailers that can
attach/detach trucks easily to serve less-than-truckload shipping, and
the RRVRP and the TSRP aim to attain high use rates for tractors in
different full truckload shipping practices. The three forms of the CTRP
share a number of common features. In particular, most of the
formulations and heuristic strategies developed for specific problems
share many similar characteristics. The CTRP is an extremely rich and
promising operations research field. More general formulations and more
general-purpose solvers are necessary to address practical combination
truck routing applications efficiently and in a timely manner. (C) 2016
The Authors. Published by Elsevier Ltd.
BibTeX: 
@inproceedings{ISI:000370820100075,
  author = {Li, Hongqi and Lv, Tan and Lu, Yingrong},
  editor = {Wang, W and Bengler, K and Wets, G and Shen, Y and Jiang, X},
  title = {The Combination Truck Routing Problem: A Survey},
  booktitle = {GREEN INTELLIGENT TRANSPORTATION SYSTEM AND SAFETY},
  year = {2016},
  volume = {138},
  pages = {639-648},
  note = {6th International Conference on Green Intelligent Transportation System and Safety (GITSS), Beijing, PEOPLES R CHINA, JUL 02-06, 2016},
  doi = {{10.1016/j.proeng.2016.01.301}}
}
2015
5Kota L and Jarmai K (2015), Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming, APPLIED MATHEMATICAL MODELLING., JUN 15, 2015. Vol. 39(12), pp. 3410-3433.

[Abstract] [BibTeX] [DOI]
Abstract: This study describes a single phase algorithm for the fixed destination
multi-depot multiple traveling salesman problem with multiple tours
(mdmTSP). This problem widely appears in the field of logistics mostly
in connection with maintenance networks. The general model of the
technical inspection and maintenance systems is shown in the first part,
where the solution of this problem is an important question. A
mathematical model of the system's object expert assignment is proposed
with the constraints typical of the system, like experts' capacity
minimum and maximum and constraints on maximum and daily tours of the
experts. In the second part, the developed evolutionary programming
algorithm is described which solves the assignment, regarding the
constraints introducing penalty functions in the algorithm. In the last
part of the paper, the convergence of the algorithm and the run times
and some examination of the parallelization are presented. (C) 2014
Elsevier Inc. All rights reserved.
BibTeX: 
@article{ISI:000355890200018,
  author = {Kota, L. and Jarmai, K.},
  title = {Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming},
  journal = {APPLIED MATHEMATICAL MODELLING},
  year = {2015},
  volume = {39},
  number = {12},
  pages = {3410-3433},
  doi = {10.1016/j.apm.2014.11.043}
}
6Vidal T, Battarra M, Subramanian A and Erdogan G (2015), Hybrid metaheuristics for the Clustered Vehicle Routing Problem, COMPUTERS & OPERATIONS RESEARCH., JUN, 2015. Vol. 58, pp. 87-99.

[Abstract] [BibTeX] [DOI]
Abstract: The Clustered Vehicle Routing Problem (CluVRP) is a variant of the
Capacitated Vehicle Routing Problem in which customers are grouped into
clusters. Each cluster has to be visited once, and a vehicle entering a
cluster cannot leave it until all customers have been visited. This
paper presents two alternative hybrid metaheuristic algorithms for the
CluVRP. The first algorithm is based on an Iterated Local Search
algorithm, in which only feasible solutions are explored and
problem-specific local search moves are utilized. The second algorithm
is a hybrid genetic search, for which the shortest Hamiltonian path
between each pair of vertices within each cluster should be precomputed.
Using this information, a sequence of clusters can be used as a solution
representation and large neighborhoods can be efficiently explored, by
means of bi-directional dynamic programming, sequence concatenation, and
appropriate data structures. Extensive computational experiments are
performed on benchmark instances from the literature, as well as new
large scale instances. Recommendations on the choice of algorithm are
provided, based on average cluster size. (C) 2014 Elsevier Ltd. All
rights reserved.
BibTeX: 
@article{ISI:000351967100009,
  author = {Vidal, Thibaut and Battarra, Maria and Subramanian, Anand and Erdogan, Guenes},
  title = {Hybrid metaheuristics for the Clustered Vehicle Routing Problem},
  journal = {COMPUTERS & OPERATIONS RESEARCH},
  year = {2015},
  volume = {58},
  pages = {87-99},
  doi = {10.1016/j.cor.2014.10.019}
}
7Biesinger B, Hu B and Raidl GR (2015), A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands, In EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2015. Vol. 9026, pp. 48-60.

[Abstract] [BibTeX] [DOI]
Abstract: In this work we consider the generalized vehicle routing problem with
stochastic demands (GVRPSD) being a combination of the generalized
vehicle routing problem, in which the nodes are partitioned into
clusters, and the vehicle routing problem with stochastic demands, where
the exact demands of the nodes are not known beforehand. It is an
NP-hard problem for which we propose a variable neighborhood search
(VNS) approach to minimize the expected tour length through all
clusters. We use a permutation encoding for the cluster sequence and
consider the preventive restocking strategy where the vehicle restocks
before it potentially runs out of goods. The exact solution evaluation
is based on dynamic programming and is very time-consuming. Therefore we
propose a multi-level evaluation scheme to significantly reduce the time
needed for solution evaluations. Two different algorithms for finding an
initial solution and three well-known neighborhood structures for
permutations are used within the VNS. Results show that the multi-level
evaluation scheme is able to drastically reduce the overall run-time of
the algorithm and that it is essential to be able to tackle larger
instances. A comparison to an exact approach shows that the VNS is able
to find an optimal or near-optimal solution in much shorter time.
BibTeX: 
@inproceedings{ISI:000361701400005,
  author = {Biesinger, Benjamin and Hu, Bin and Raidl, Guenther R.},
  editor = {Ochoa, G and Chicano, F},
  title = {A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands},
  booktitle = {EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2015},
  year = {2015},
  volume = {9026},
  pages = {48-60},
  note = {15th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP), Copenhagen, DENMARK, APR 08-10, 2015},
  doi = {10.1007/978-3-319-16468-7\_5}
}
2014
8Pop P and Chira C (2014), A Hybrid Approach based on Genetic Algorithms for Solving the Clustered Vehicle Routing Problem, In 2014 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC)., pp. 1421-1426.

[Abstract] [BibTeX]
Abstract: In this paper, we describe a hybrid approach based on the use of genetic
algorithms for solving the Clustered Vehicle Routing Problem, denoted by
CluVRP. The problem studied in this work is a generalization of the
classical Vehicle Routing Problem (VRP) and is closely related to the
Generalized Vehicle Routing Problem (GVRP). Along with the genetic
algorithm, we consider a local-global approach to the problem that is
reducing considerably the size of the solutions space. The obtained
computational results point out that our algorithm is an appropriate
method to explore the search space of this complex problem and leads to
good solutions in a reasonable amount of time.
BibTeX: 
@inproceedings{ISI:000356684602014,
  author = {Pop, Petrica and Chira, Camelia},
  title = {A Hybrid Approach based on Genetic Algorithms for Solving the Clustered Vehicle Routing Problem},
  booktitle = {2014 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC)},
  year = {2014},
  pages = {1421-1426},
  note = {IEEE Congress on Evolutionary Computation (CEC), Beijing, PEOPLES R CHINA, JUL 06-11, 2014}
}
9Battarra M, Erdogan G and Vigo D (2014), Exact Algorithms for the Clustered Vehicle Routing Problem, OPERATIONS RESEARCH., JAN-FEB, 2014. Vol. 62(1), pp. 58-71.

[Abstract] [BibTeX] [link]
Abstract: This study presents new exact algorithms for the clustered vehicle
routing problem (CluVRP). The CluVRP is a generalization of the
capacitated vehicle routing problem (CVRP), in which the customers are
grouped into clusters. As in the CVRP, all the customers must be visited
exactly once, but a vehicle visiting one customer in a cluster must
visit all the remaining customers therein before leaving it. Based on an
exponential time preprocessing scheme, an integer programming
formulation for the CluVRP is presented. The formulation is enhanced by
a polynomial time graph reduction scheme. Two exact algorithms for the
CluVRP, a branch and cut as well as a branch and cut and price, are
presented. The computational performances of the algorithms are tested
on benchmark instances adapted from the vehicle routing problem
literature as well as real-world instances from a solid waste collection
application.
BibTeX: 
@article{ISI:000332013300004,
  author = {Battarra, Maria and Erdogan, Guenes and Vigo, Daniele},
  title = {Exact Algorithms for the Clustered Vehicle Routing Problem},
  journal = {OPERATIONS RESEARCH},
  year = {2014},
  volume = {62},
  number = {1},
  pages = {58-71},
  doi = {10.1287/opre.2013.1227}
}
2013
10Stanojevic M, Stanojevic B and Vujosevic M (2013), Enhanced savings calculation and its applications for solving capacitated vehicle routing problem, APPLIED MATHEMATICS AND COMPUTATION., JUN 15, 2013. Vol. 219(20), pp. 10302-10312.

[Abstract] [BibTeX] [DOI]
Abstract: The vehicle routing problem (VRP) is one of the most explored
combinatorial problems in operations research. A very fast and simple
algorithm that solves the VRP is the well known Clarke-Wright savings
algorithm. In this paper we introduce a new way of merging routes and
the corresponding formula for calculating savings. We also apply the
enhanced merging to develop a new heuristic -Extended Savings Algorithm
(ESA) that dynamically recalculates savings during iterations.
Computational results show that, on average ESA gives better solutions
than the original savings algorithm. Implementing randomization of some
steps of our heuristic we obtained even better results which competes
with more complex and well known heuristics. The ESA is further used to
generate good routes as part of a setcovering- based algorithm for the
Capacitated VRP (CVRP). The numerical results of our experiments are
reported. (C) 2013 Elsevier Inc. All rights reserved.
BibTeX: 
@article{ISI:000319499800017,
  author = {Stanojevic, Milan and Stanojevic, Bogdana and Vujosevic, Mirko},
  title = {Enhanced savings calculation and its applications for solving capacitated vehicle routing problem},
  journal = {APPLIED MATHEMATICS AND COMPUTATION},
  year = {2013},
  volume = {219},
  number = {20},
  pages = {10302-10312},
  doi = {10.1016/j.amc.2013.04.002}
}
11Pop PC, Matei O and Sitar CP (2013), An improved hybrid algorithm for solving the generalized vehicle routing problem, NEUROCOMPUTING., JUN 3, 2013. Vol. 109(SI), pp. 76-83.

[Abstract] [BibTeX] [DOI]
Abstract: The generalized vehicle routing problem (GVRP) is a natural extension of
the classical vehicle routing problem (VRP). In GVRP, we are given a
partition of the customers into groups (clusters) and a depot and we
want to design a minimum length collection of routes for the fleet of
vehicles, originating and terminating at the depot and visiting exactly
one customer from each group, subject to capacity restrictions. The aim
of this paper is to present an efficient hybrid heuristic algorithm
obtained by combining a genetic algorithm (GA) with a local-global
approach to the GVRP and a powerful local search procedure. The
computational experiments on several benchmark instances show that our
hybrid algorithm is competitive to all of the known heuristics published
to date. (C) 2012 Elsevier B.V. All rights reserved.
BibTeX: 
@article{ISI:000318379600010,
  author = {Pop, Petrica C. and Matei, Oliviu and Sitar, Corina Pop},
  title = {An improved hybrid algorithm for solving the generalized vehicle routing problem},
  journal = {NEUROCOMPUTING},
  year = {2013},
  volume = {109},
  number = {SI},
  pages = {76-83},
  doi = {10.1016/j.neucom.2012.03.032}
}
12Drexl M (2013), Applications of the vehicle routing problem with trailers and transshipments, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH., JUN 1, 2013. Vol. 227(2), pp. 275-283.

[Abstract] [BibTeX] [DOI]
Abstract: The vehicle routing problem with trailers and transshipments (VRPTT) is
a recent and challenging extension of the well-known vehicle routing
problem. The VRPTT constitutes an archetypal representative of the class
of vehicle routing problems with multiple synchronization constraints
(VRPMSs). In addition to the usual task covering constraints, VRPMSs
require further synchronization between vehicles, concerning spatial,
temporal, and load aspects. VRPMSs possess considerable practical
relevance, but limited coverage in the scientific literature. The
purpose of the present paper is to describe how several important types
of VRPMSs, such as multi-echelon location-routing problems and
simultaneous vehicle and crew routing problems, can be modelled as
VRPTTs. (C) 2012 Elsevier B.V. All rights reserved.
BibTeX: 
@article{ISI:000315080300005,
  author = {Drexl, Michael},
  title = {Applications of the vehicle routing problem with trailers and transshipments},
  journal = {EUROPEAN JOURNAL OF OPERATIONAL RESEARCH},
  year = {2013},
  volume = {227},
  number = {2},
  pages = {275-283},
  doi = {10.1016/j.ejor.2012.12.015}
}
13Naji-Azimi Z and Salari M (2013), A complementary tool to enhance the effectiveness of existing methods for heterogeneous fixed fleet vehicle routing problem, APPLIED MATHEMATICAL MODELLING., MAR 15, 2013. Vol. 37(6), pp. 4316-4324.

[Abstract] [BibTeX] [DOI]
Abstract: The heterogeneous fixed fleet vehicle routing problem (HFFVRP) is a
variant of the standard vehicle routing problem (VRP), in which the
vertices have to be served using a fixed number of vehicles that could
be different in size and fixed or variable costs. In this article, we
propose an integer linear programming-based heuristic approach in order
to solve the HFFVRP that could be used as a complementary tool to
improve the performance of the existing methods of solving this problem.
Computational results show the effectiveness of the proposed method. (C)
2012 Elsevier Inc. All rights reserved.
BibTeX: 
@article{ISI:000316706300056,
  author = {Naji-Azimi, Zahra and Salari, Majid},
  title = {A complementary tool to enhance the effectiveness of existing methods for heterogeneous fixed fleet vehicle routing problem},
  journal = {APPLIED MATHEMATICAL MODELLING},
  year = {2013},
  volume = {37},
  number = {6},
  pages = {4316-4324},
  doi = {10.1016/j.apm.2012.09.027}
}
14Riera-Ledesma J and Jose Salazar-Gonzalez J (2013), A column generation approach for a school bus routing problem with resource constraints, COMPUTERS & OPERATIONS RESEARCH., FEB, 2013. Vol. 40(2), pp. 566-583.

[Abstract] [BibTeX] [DOI]
Abstract: The Multiple Vehicle Traveling Purchaser Problem describes a school bus
routing problem that combines bus stop selection and bus route
generation. This problem aims at selecting a set of bus stops from among
a group of potential locations to pick up students, and for designing
bus routes to visit the selected stops and to carry the students to
their school. We address a variation of this problem that considers
certain constraints on each bus route, such as bounds on the distances
traveled by the students, bounds on the number of visited bus stops, and
bounds on the minimum number of students that a vehicle has to pick up.
Since column generation methods can easily deal with constraints on the
consumption of resources related to each column, such as the constraints
on routes mentioned above, and these methods are an alternative to other
approaches based on three index variable formulations which suffer from
the drawback of symmetry, we propose a branch-and-price algorithm based
on a set partitioning formulation for this problem.
We also study, using an extensive computational experience, the impact
of enriching our proposal with additional inequalities in a
branch-and-cut-and-price algorithm, which has revealed the importance of
supplementing our column generation algorithm with cuts to improve its
performance. (C) 2012 Elsevier Ltd. All rights reserved.
BibTeX: 
@article{ISI:000311533900006,
  author = {Riera-Ledesma, Jorge and Jose Salazar-Gonzalez, Juan},
  title = {A column generation approach for a school bus routing problem with resource constraints},
  journal = {COMPUTERS & OPERATIONS RESEARCH},
  year = {2013},
  volume = {40},
  number = {2},
  pages = {566-583},
  doi = {10.1016/j.cor.2012.08.011}
}
15Li H, Li Y, Lu Y, Song Q and Zhang J (2013), The Effects of the Tractor and Semitrailer Routing Problem on Mitigation of Carbon Dioxide Emissions, DISCRETE DYNAMICS IN NATURE AND SOCIETY.

[Abstract] [BibTeX] [DOI]
Abstract: The incorporation of CO2 emissions minimization in the vehicle routing
problem (VRP) is of critical importance to enterprise practice. Focusing
on the tractor and semitrailer routing problem with full truckloads
between any two terminals of the network, this paper proposes a
mathematical programming model with the objective of minimizing CO2
emissions per ton-kilometer. A simulated annealing (SA) algorithm is
given to solve practical-scale problems. To evaluate the performance of
the proposed algorithm, a lower bound is developed. Computational
experiments on various problems generated randomly and a realistic
instance are conducted. The results show that the proposed methods are
effective and the algorithm can provide reasonable solutions within an
acceptable computational time.
BibTeX: 
@article{ISI:000328990900001,
  author = {Li, Hongqi and Li, Yanran and Lu, Yue and Song, Qiang and Zhang, Jun},
  title = {The Effects of the Tractor and Semitrailer Routing Problem on Mitigation of Carbon Dioxide Emissions},
  journal = {DISCRETE DYNAMICS IN NATURE AND SOCIETY},
  year = {2013},
  doi = {10.1155/2013/809135}
}
16Li H, Li Y, Zhao Q, Lu Y and Song Q (2013), The Tractor and Semitrailer Routing Considering Carbon Dioxide Emissions, MATHEMATICAL PROBLEMS IN ENGINEERING.

[Abstract] [BibTeX] [DOI]
Abstract: The incorporation of the minimization of carbon dioxide (CO2) emissions
in the VRP is important to logistics companies. The paper deals with the
tractor and semitrailer routing problem with full truckload between any
two depots of the network; an integer programming model with the
objective of minimizing CO2 emissions per ton-kilometer is proposed. A
two-stage approach with the same core steps of the simulated annealing
(SA) in both stages is designed. The number of tractors is provided in
the first stage and the CO2 emissions per ton-kilometer are then
optimized in the second stage. Computational experiments on small-scale
randomly generated instances supported the feasibility and validity of
the heuristic algorithm. To a practical-scale problem, the SA algorithm
can provide advice on the number of tractors, the routes, and the
location of the central depot to realize CO2 emissions decrease.
BibTeX: 
@article{ISI:000328973300001,
  author = {Li, Hongqi and Li, Yanran and Zhao, Qiuhong and Lu, Yue and Song, Qiang},
  title = {The Tractor and Semitrailer Routing Considering Carbon Dioxide Emissions},
  journal = {MATHEMATICAL PROBLEMS IN ENGINEERING},
  year = {2013},
  doi = {10.1155/2013/509160}
}