Asymmetric Multidepot Vehicle Routing Problems : Valid Inequalities and a Branch-and-Cut Algorithm | PERPUSTAKAAN UNIVERSITAS KATOLIK PARAHYANGAN

Pencarian berdasarkan :

Pencarian terakhir:

Text

Asymmetric Multidepot Vehicle Routing Problems : Valid Inequalities and a Branch-and-Cut Algorithm

Broek, Michiel A. J. uit het - Nama Orang; Roodbergen, Kees Jan - Nama Orang; Coelho, Leandro C. - Nama Orang; Jargalsaikhan, Bolor - Nama Orang; Schrotenboer, Albert H. - Nama Orang;

We present a generic branch-and-cut framework for solving routing problems with multiple depots and asymmetric cost structures, which determines a set of cost-minimizing (capacitated) vehicle tours that fulfill a set of customer demands. The backbone of the framework is a series of valid inequalities with corresponding separation algorithms that exploit the asymmetric cost structure in directed graphs. We derive three new classes of so-called Dk inequalities that eliminate subtours, enforce tours to be linked to a single depot, and impose bounds on the number of customers in a tour. In addition, other well-known valid inequalities for solving vehicle routing problems are generalized and adapted to be valid for routing problems with multiple depots and asymmetric cost structures. The framework is tested on four specific problem variants, for which we develop a new set of large-scale benchmark instances. The results show that the new inequalities can reduce root-node optimality gaps by up to 67.2% compared with existing approaches. Moreover, the complete framework is very effective and can solve instances of considerably larger size than reported in the literature. For instance, it solves asymmetric multidepot traveling-salesman-problem instances containing up to 400 customers and 50 depots, whereas to date only solutions of instances containing up to 300 customer nodes and 60 depots have been reported.

Ketersediaan

Barcode		Tipe Koleksi	Nomor Panggil	Lokasi	Status
art139394	null	Artikel		Gdg9-Lt3	Tersedia namun tidak untuk dipinjamkan - No Loan

Informasi Detail

Judul Seri: OPERATIONS RESEARCH; Vol.69 No.2 March-April 2021
No. Panggil: -
Penerbit: : .,
Deskripsi Fisik: p. 380 - 409
Bahasa: English
ISBN/ISSN: -
Klasifikasi: -
Tipe Isi: -
Tipe Media: -
Tipe Pembawa: -
Edisi: -
Subjek: VALID INEQUALITIES
VEHICLE ROUTING
BRANCH-AND-CUT
ASYMMETRIC
MULTIDEPOT
UPPER-BOUND PROCEDURE
Info Detail Spesifik: https://doi.org/10.1287/opre.2020.2033
Pernyataan Tanggungjawab: Michiel A. J. uit het Broek, Albert H. Schrotenboer, Bolor Jargalsaikhan, Kees Jan Roodbergen, Leandro C. Coelho

Versi lain/terkait

Tidak tersedia versi lain

Lampiran Berkas

Tidak Ada Data

Komentar

Anda harus masuk sebelum memberikan komentar