e-journal

Beam Search Combined With MAX-MIN Ant Systems and Benchmarking Data Tests for Weighted Vehicle Routing Problem

---

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. TheWVRP 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 theWVRP 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 theWVRP can increase
cost savings for the instances with a dispersed customer distribution and a large weight.
Note to Practitioners—The VRP is a well-known operations research model for a class of transportation and logistics management problems in industrial systems. Large-scale problems arise in practice in production systems, e.g., charge planning, casting planning, and rolling planning in an iron-steel making process, which can be formulated as variants of the VRP model. This paper is motivated by practical needs for clean production and cost-savings, lower carbon emission policies and the observation that most VRP models neglect the effect of the cargo weight on the total costs. The WVRP model incorporates the cargo weight into the optimization objective function, resulting in an exact formulation. This model can be applied to logistics and transportation management problems in industrial systems and is particularly useful given the mandatory lower carbon emissions policy. The WVRP model results in higher cost savings than traditional VRP models for instances with a dispersed customer distribution and a large weight. The BEAM-MMAS algorithm combines beam search and MAX-MIN ant systems and has been shown to be an effective algorithm for solving such problems; this algorithm can be used to ensure high quality solutions for medium-scale problems. For largescale problems, the MMAS algorithm can produce a satisfactory solution in less time than the BEAM-MMAS algorithm.
Index Terms—Ant colony algorithm, beam search, benchmarking data testing, meta-heuristics, weighted vehicle routing problem.

---

Ketersediaan

Tidak ada salinan data

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING

No. Panggil

-

Penerbit

New York : IEEE., 2014

Deskripsi Fisik

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 11, NO. 4, OCTOBER 2014

Bahasa

English

ISBN/ISSN

1545-5955

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

VOL. 11, NO. 4, OCTOBER 2014

Subjek

TEKNIK

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Yuli/Agus

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar