Smart Delivery Systems: Solving Complex Vehicle Routing Problems

Cover
Smart Delivery Systems:

Solving Complex Vehicle Routing Problems
Copyright
Dedication
Contents
Contributors
1 Current and emerging formulations and models of real-life rich vehicle routing problems
	1.1 Introduction
	1.2 Vehicle Routing Problem and its variants
		1.2.1 The classical Vehicle Routing Problem
		1.2.2 Variants of the VRP
		1.2.3 Green Vehicle Routing Problem (GVRP)
		1.2.4 Electric Vehicle Routing Problem (EVRP)
		1.2.5 Algorithms for solving the VRP and its variants
	1.3 Bus Routing Problem and its variants
		1.3.1 Bicriterion Bus Routing Problem (BBRP)
			1.3.1.1 Formulation of the BBRP
			1.3.1.2 Analysis of the BBRP
			1.3.1.3 Algorithms for solving the BBRP
		1.3.2 Multicriteria Bus Routing Problem (MBRP)
		1.3.3 School Bus Routing Problem (SBRP)
			1.3.3.1 Data preparation
			1.3.3.2 Bus stop selection
			1.3.3.3 Bus route generation
			1.3.3.4 School bell time adjustment
			1.3.3.5 Route scheduling
			1.3.3.6 Means of transport
			1.3.3.7 Objectives of the problem
			1.3.3.8 Algorithms for solving the SBRP and its variants
			1.3.3.9 Real school bus networks
		1.3.4 Other selected variants of the Bus Routing Problem
	1.4 Unmanned Vehicle Routing Problem
	1.5 The other routing problems of electric vehicles
	1.6 Conclusions
	Acknowledgment
	References
2 On a road to optimal fleet routing algorithms: a gentle introduction to the state-of-the-art
	2.1 Introduction
	2.2 Optimal Route Choice problem
		2.2.1 Introduction
		2.2.2 Discrete choice models
		2.2.3 Shortest Path problem
		2.2.4 Traffic Assignment problem
			2.2.4.1 Deterministic traffic assignment
				2.2.4.1.1 Wardrop principles
			2.2.4.2 Stochastic extensions for Traffic Assignment problem
			2.2.4.3 Solution methods for Traffic Assignment problem
				2.2.4.3.1 Comparison of performance between solution methods
	2.3 Traveling Salesman Problem
		2.3.1 Introduction
		2.3.2 TSP and its generalizations
			2.3.2.1 Asymmetric TSP
			2.3.2.2 Precedence-constrained TSP
			2.3.2.3 TSP with time windows
		2.3.3 Exact methods
			2.3.3.1 Held-Karp algorithm
			2.3.3.2 Branch-and-bound algorithm
			2.3.3.3 Branch-and-cut algorithm
			2.3.3.4 Exact algorithms for TSP and ATSP
				2.3.3.4.1 Exact methods for PCTSP and TSPTW
		2.3.4 Approximate solutions
			2.3.4.1 Types of approximate algorithms
				2.3.4.1.1 Constructive heuristics
					2.3.4.1.1.1 Insertion heuristics
					2.3.4.1.1.2 Local searches
					2.3.4.1.1.3 Heuristics based on constructing spanning trees
				2.3.4.1.2 Improvement heuristics
					2.3.4.1.2.1 k-opt heuristics
					2.3.4.1.2.2 Lin-Kernighan heuristics
				2.3.4.1.3 Nature inspired algorithms
					2.3.4.1.3.1 Artificial neural networks
					2.3.4.1.3.2 Metaheuristics
						2.3.4.1.3.2.1 Genetic algorithms
						2.3.4.1.3.2.2 Simulated annealing
						2.3.4.1.3.2.3 Algorithms based on social behavior of animals
						2.3.4.1.3.2.4 Water wave algorithm
						2.3.4.1.3.2.5 Other nature-inspired metaheuristics
			2.3.4.2 Approximate algorithms for TSP and ATSP
			2.3.4.3 Approximate algorithms for PCTSP and TSPTW
		2.3.5 Quantum algorithms
			2.3.5.1 Qubit
			2.3.5.2 Quantum annealing
			2.3.5.3 Algorithms
		2.3.6 Computational complexity
	2.4 Vehicle Routing Problem
		2.4.1 Introduction
		2.4.2 Taxonomy
			2.4.2.1 Variants of CVRP
				2.4.2.1.1 Heterogeneous fleet
				2.4.2.1.2 Multicompartment vehicles
				2.4.2.1.3 Pollution-Routing Problem
				2.4.2.1.4 Split deliveries VRP
				2.4.2.1.5 Time-Dependent VRP
		2.4.3 Capacitated Vehicle Routing Problem
			2.4.3.1 Mathematical formulation
			2.4.3.2 Exact solutions
				2.4.3.2.1 Dynamic programming
				2.4.3.2.2 Integer linear programming
					2.4.3.2.2.1 Vehicle flow formulations
					2.4.3.2.2.2 Set partitioning formulas
			2.4.3.3 Heuristics for CVRP
				2.4.3.3.1 Constructive heuristics
				2.4.3.3.2 Two-phase heuristics
				2.4.3.3.3 Improvement heuristics
				2.4.3.3.4 Conclusions
			2.4.3.4 Metaheuristics for CVRP
		2.4.4 Vehicle Routing Problem with time windows
			2.4.4.1 Definition
			2.4.4.2 Exact solutions
			2.4.4.3 Heuristics for VRPTW
				2.4.4.3.1 Route-building heuristics
				2.4.4.3.2 Route improvement heuristics
				2.4.4.3.3 Composite heuristics
			2.4.4.4 Metaheuristics for VRPTW
		2.4.5 Pickup and Delivery Vehicle Routing Problem
			2.4.5.1 Definition
			2.4.5.2 Heuristics for PDPTW
			2.4.5.3 Metaheuristics for PDPTW
				2.4.5.3.1 Guided ejection search
				2.4.5.3.2 Memetic Algorithm
	2.5 Conclusions
	Acknowledgments
	References
3 Exact algorithms for solving rich vehicle routing problems
	3.1 Branch-and-bound methods
	3.2 Branch-and-cut methods
	3.3 Branch-and-price methods
	3.4 Branch-and-cut-and-price methods
	3.5 Constraint Programming
	3.6 Summary
	References
4 Heuristics, metaheuristics, and hyperheuristics for rich vehicle routing problems
	4.1 Heuristics for rich vehicle routing problems
		4.1.1 Construction heuristics
		4.1.2 Improvement heuristics
	4.2 Metaheuristics for rich vehicle routing problems
		4.2.1 Simulated Annealing
		4.2.2 Tabu Search
		4.2.3 Adaptive Memory Procedures
		4.2.4 Variable Neighborhood Search
		4.2.5 Large Neighborhood Search
		4.2.6 Greedy Randomized Adaptive Search Procedure
		4.2.7 Particle Swarm Optimization
		4.2.8 Ant Colony Algorithms
		4.2.9 Artificial Bee Colony Algorithms
		4.2.10 Bat Algorithms
		4.2.11 Cuckoo search
		4.2.12 Firefly Algorithms
		4.2.13 Golden Ball Algorithms
		4.2.14 Gravitational Search Algorithm
		4.2.15 Bacterial Foraging Optimization Algorithm
		4.2.16 Genetic and Evolutionary Algorithms
		4.2.17 Memetic Algorithms
	4.3 Hyperheuristics for rich vehicle routing problems
	4.4 Summary
	References
5 Hybrid algorithms for rich vehicle routing problems: a survey
	5.1 Introduction
		5.1.1 Methodology and contribution of this chapter
		5.1.2 Structure of the chapter
	5.2 Mathematical model for traditional CVRP
		5.2.1 Objective function
		5.2.2 Problem constraints
		5.2.3 Flow constraint
		5.2.4 Capacity constraint
		5.2.5 The mathematical model of classical VRP
	5.3 From traditional VRP to rich VRP
		5.3.1 Traditional VRP
		5.3.2 Traditional advanced VRP
		5.3.3 Rich VRP & real-life VRP
		5.3.4 Rich VRP definition
	5.4 Solution approaches for RVRPs
	5.5 Literature review of hybrid approaches for VRPs
		5.5.1 Real-life VRP (distribution system)
			5.5.1.1 Food industry
			5.5.1.2 Waste collection management
			5.5.1.3 Oil, fuel, and gas
			5.5.1.4 News paper delivery
		5.5.2 Rich VRP
	5.6 Conclusion and future directions
	References
6 Parallel algorithms for solving rich vehicle routing problems
	6.1 Parallelism ideas and taxonomies
	6.2 Cooperative search strategies
	6.3 Parallel tabu search
	6.4 Parallel genetic and evolutionary algorithms
	6.5 Parallel memetic algorithms
	6.6 Parallel ant colony algorithms
	6.7 Parallel simulated annealing
	6.8 Summary
	References
7 Where machine learning meets smart delivery systems
	7.1 Introduction
		7.1.1 A gentle introduction to machine learning
		7.1.2 Where machine learning meets smart delivery systems - an overview
		7.1.3 Structure of this chapter
	7.2 Tuning hyper-parameters of existent algorithms for solving rich vehicle routing problems using machine learning
	7.3 Solving rich vehicle routing problems using hybrid algorithms that exploit machine learning
	7.4 Solving rich vehicle routing problems using data-driven machine learning algorithms
	7.5 Summary
	Acknowledgments
	References
8 How to assess your Smart Delivery System?
	8.1 Introduction
	8.2 Literature review
	8.3 Notation and definition
	8.4 Model description
		8.4.1 Generating delivery points
		8.4.2 Defining the weight between a pair of deliveries
		8.4.3 The benchmark tool
		8.4.4 Modeling Manhattan (NY) streets
	8.5 Real-world PostVRP benchmark (RWPostVRPB)
	8.6 Final remarks and conclusion
	Acknowledgments
	References
9 Practical applications of smart delivery systems
	9.1 Introduction
	9.2 Literature review
		9.2.1 Routing in emergencies
		9.2.2 Rich vehicle routing problems
	9.3 Mine evacuation as a rich VRP
	9.4 Evacuation scenario examples
	9.5 Summary and future work
	References
Index
Back Cover