Paper Info
Title
Beam Search Combined With MAX-MIN Ant Systems and Benchmarking Data Tests for Weighted Vehicle Routing Problem
Abstract
In real-world cargo transportation, there are charges associated with both the traveling distance and the loading quantity. Cargo trucks must comply with a mandatory lower carbon emissions policy: the emissions of large-volume cargo truck/containers depend greatly on the cargo loading and the traveling distance. To address this issue, instead of assuming a constant vehicle loading from one customer to another, a variable vehicle loading should be used in optimizing the vehicle routine, which is known as a weighted vehicle routing problem (WVRP) model. The WVRP is an NP-hard problem; thus, the purpose of this paper is to develop a BEAM-MMAS algorithm that combines a MAX-MIN ant system with beam search to show that the WVRP is more effective than the VRP and to determine the types of VRP instances for which the WVRP has more cost-savings than the VRP. To this end, computational experiments are carried out on benchmark problems of the capacitated VRP for seven types of distributions, and the effectiveness of the BEAM-MMAS algorithm is compared with that of general ACO and MMAS algorithms for large-size benchmarking instances. The benchmarking tests show that lower operation costs are produced using the WVRP than using the optimal or best known paths of the CVRP and that the WVRP can increase cost savings for the instances with a dispersed customer distribution and a large weight.
Year
DOI
Venue
2014
10.1109/TASE.2013.2295092
IEEE T. Automation Science and Engineering
Keywords
Field
DocType
Vehicle routing,Benchmark testing,Ant colony optimization,NP-hard problem
Truck,Ant colony optimization algorithms,Vehicle routing problem,Mathematical optimization,Computer science,Beam search,Benchmarking
Journal
Volume
Issue
ISSN
11
4
1545-5955
Citations 
PageRank 
References 
5
0.41
19
Authors
4
Name
Order
Citations
PageRank
Jiafu Tang154149.29
Jing Guan250.41
Yang Yu350.41
Jinyu Chen4236.33