NDLI: A new Tabu Search heuristic algorithm for the Vehicle Routing Problem with Time Windows

Content Provider	IEEE Xplore Digital Library
Author	Qi Ming-yao Miao Li-xin Zhang Le Xu Hua-yu
Copyright Year	2008
Description	Author affiliation: Grad. Sch. at Shenzhen, Tsinghua Univ., Shenzhen (Qi Ming-yao; Miao Li-xin) \|\| Dept. of Math. Sci., Tsinghua Univ., Beijing (Zhang Le; Xu Hua-yu)
Abstract	This paper describes a new design of Tabu search (ts) algorithm for solving the vehicle routing problem with time windows (VRPTW). Since VRPTW is a well known NP-hard problem, heuristic algorithms such as Tabu search are always used to get a good approach. The former published designs of TS usually focus on the neighbor structure, the relaxation to the objective function or the multi-period algorithms. This paper has two contributions. First, it designs an objective value-based Tabu List structure to help decreasing the Tabu list size and escape from local optima. it still adopts some tactics like adaptive Tabu size, randomly selected neighbor structure and so on. Second, from a problem oriented point of view, it shows that, with this self-adaptive Tabu list, even five kinds of simple neighbor structures and a single period algorithm with original objective function can get very good solutions. We tested this algorithm with Solomonpsilas VRPTW benchmark problems, and 7 of the best known solutions are updated. Another advantage of this algorithm is its efficiency. It runs on an average of 80 seconds on a normal personal computer for a solution of a problem with 100 customers.
Starting Page	1648
Ending Page	1653
File Size	365234
Page Count	6
File Format	PDF
ISBN	9781424423873
DOI	10.1109/ICMSE.2008.4669126
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-09-10
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Heuristic algorithms Conference management Routing Partitioning algorithms time window Vehicles Automotive engineering genetic algorithm heuristic algorithm Design engineering NP-hard problem Engineering management Tabu search vehicle routing problem
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Genetic algorithm for vehicle routing problem with time window with uncertain vehicle number

A Hybrid Search Algorithm for the Vehicle Routing Problem with Time Windows (2001)

A research on routing problems of multi-vehicle in single parking with time windows

Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles

A Variable Neighborhood Tabu Search Algorithm for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows

Solving Vehicle Routing Problem with Time Window Constraints

Research on vehicle routing problem with soft time windows based on tabu search algorithm

A Spatio-temporal Distance Based Two-Phase Heuristic Algorithms for Vehicle Routing Problem

Hybrid Genetic Tabu Search Simulated Annealing Algorithm and its application in vehicle routing problem with time windows

A new Tabu Search heuristic algorithm for the Vehicle Routing Problem with Time Windows

Similar Documents

Genetic algorithm for vehicle routing problem with time window with uncertain vehicle number

A Hybrid Search Algorithm for the Vehicle Routing Problem with Time Windows (2001)

A research on routing problems of multi-vehicle in single parking with time windows

Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles

A Variable Neighborhood Tabu Search Algorithm for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows

Solving Vehicle Routing Problem with Time Window Constraints

Research on vehicle routing problem with soft time windows based on tabu search algorithm

A Spatio-temporal Distance Based Two-Phase Heuristic Algorithms for Vehicle Routing Problem

Hybrid Genetic Tabu Search Simulated Annealing Algorithm and its application in vehicle routing problem with time windows

A new Tabu Search heuristic algorithm for the Vehicle Routing Problem with Time Windows