An Intelligent Water Drop Algorithm for Solving Multi-Objective Vehicle Routing Problems With Mixed Time Windows

An Intelligent Water Drop Algorithm for Solving Multi-Objective Vehicle Routing Problems With Mixed Time Windows

Tao Wang (Business School, University of Shanghai for Science and Technology, Shanghai, China), Jing Ni (Business School, University of Shanghai for Science and Technology, Shanghai, China) and Yixuan Wang (Business School, University of Shanghai for Science and Technology, Shanghai, China)
Copyright: © 2019 |Pages: 23
DOI: 10.4018/IJSDS.2019010106

Abstract

This article proposes an Intelligent Water Drop Algorithm for solving Multi-Objective Vehicle Routing Problems by considering the constraints of vehicle volume, delivery mileage, and mixed time windows and minimizing the cost of distribution and the minimum number of vehicles. This article improves the basic Intelligent Water Drop Algorithm and show the improved intelligent water droplet genetic hybrid algorithm is an effective method for solving discrete problems. The authors present a practical example and show the applicability of the proposed algorithm. The authors compare the algorithms with the basic algorithm and show the improved intelligent droplet genetic hybrid algorithm has higher computing efficiency and continuous optimization capability.
Article Preview
Top

1. Introduction

Vehicle Routing Problem (VRP), first proposed by Dantzig and Ramser (1959), belong to a class of NP-hard problems in combinatorial optimization. Solomon (1987) introduced the time-window factor into VRP and proposed VRP with time window (VRPTW), also known as on-time vehicle routing problem. The realistic and theoretical research on multi-objective VRPTW is of great significance in the research community.

The VRPTW problem solving methods can be divided into two categories: the precise algorithm and the heuristic algorithm. The heuristic algorithm has the advantages of global search ability, high solution efficiency, and more practicality in solving large-scale discrete problems (Zhang and Li, 2007). Linear programming was added to solving the VRPTW and a new optimization algorithm was used to obtain a good result for the dataset with more customer points(Desrochers and Desrosiers, 1992); The two-stage genetic algorithm(GA) was applied to VRPTW, constructed a good initial solution combined with the pre-phase interpolation method, used the tabu search (TS) algorithm to conduct local search multiple times and replaced the searched solution with the new solution, and achieved good effect(Alvarenga and Mateus, 2004); The heuristic algorithm was used to solve the large-scale VRPTW, the design of a large area search method for testing a variety of vehicle routing problems, the experiments results show that about one-third of the cases in many cases have obtained the current optimal solutions, and also prove that such methods have a good effect in solving large-scale VRP (Pisinger and Ropke, 2007); In multi-objective hybrid evolutionary algorithm, chromosomes can be arbitrarily changed in length to greatly enhance their local optimization ability, which leads to a great improvement of the VRPTW solution(Tan, Yang and Goh, 2006); Based on realistic examples, the relationship between the five goals (number of vehicles, driving distance, finishing time, waiting time and delay time) were be discussed(Castro and Silva, 2011); Both the number of vehicles and the distance traveled were be considered, and obtained better results by using the improved non-dominated Sorting Genetic Algorithm (NSGA-II) algorithm (Wei and Tung, 2012).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing