notesum.ai

Published at November 26

DeepMDV: Learning Global Matching for Multi-depot Vehicle Routing Problems

cs.DB

cs.LG

Released Date: November 26, 2024

Authors: Saeed Nasehi¹, Farhana Choudhury¹, Egemen Tanin¹

Aff.: ¹The University of Melbourne

Arxiv: http://arxiv.org/abs/2411.17080v1

		Beta Distribution									Gamma Distribution
Methods		CVRP100			CVRP400			CVRP1k			CVRP100			CVRP400			CVRP1k
Methods	$\|\pazocal{D}\|$	Obj.	G(%)	T(s)	Obj.	G(%)	T(s)	Obj.	G(%)	T(s)	Obj.	G(%)	T(s)	Obj.	G(%)	T(s)	Obj.	G(%)	T(s)
HGS	2	17.1^∗	0.00	20	25.8^∗	0.00	60	45.9^∗	0.00	180	18.7^∗	0.00	20	28.0^∗	0.00	60	49.6^∗	0.00	180
Cluster + AM (bs30)		18.2	6.43	0.2	30.5	18.2	0.6	57.5	25.3	1.4	19.9	6.41	0.2	33.4	19.3	0.6	72.1	45.4	1.4
Cluster + POMO		18.0	5.26	0.2	26.5	2.71	0.7	52.1	13.5	1.7	19.6	4.81	0.2	29.8	6.42	0.7	58.4	17.7	1.7
Cluster + GLOP		19.2	12.3	0.3	27.2	5.42	1	48.6	5.9	2.7	21.5	15.0	0.3	30.6	9.28	1	54.5	9.87	2.7
MADRL		18.2	6.43	1.7	29.4	14.0	4.6	53.8	17.2	9.2	19.8	5.88	1.7	32.5	16.1	4.6	59.8	20.6	9.2
DeepMDV (AM, G)		18.1	5.84	0.4	27.1	5.03	1.7	48.7	6.1	4.1	19.5	4.27	0.4	29.0	3.57	1.7	51.9	4.63	4.1
DeepMDV (LKH3, G)		17.9	4.67	1	26.5	2.71	2.4	47.7	3.92	5.6	19.3	3.2	1	28.5	1.78	2.4	50.8	2.41	5.6
DeepMDV (LKH3, G, P)		17.7	3.5	1	26.3	1.93	2.4	47.2	2.83	5.6	19.2	2.67	1	28.3	1.07	2.4	50.5	1.81	5.6
HGS	3	15.2^∗	0.00	20	23.1^∗	0.00	60	40.6^∗	0.00	180	17.8^∗	0.00	20	26.5^∗	0.00	60	47.9^∗	0.00	180
Cluster + AM (bs30)		16.6	9.21	0.2	27.6	19.5	0.6	52.7	29.8	1.4	19.6	10.1	0.2	32.1	21.1	0.6	59.2	23.6	1.4
Cluster + POMO		16.3	7.23	0.2	24.7	6.92	0.7	49.8	22.7	1.7	19.2	7.86	0.2	28.4	7.16	0.7	56.5	17.8	1.7
Cluster + GLOP		18.2	19.7	0.4	26.3	13.9	1	45.9	13.1	2.6	20.4	14.6	0.4	29.3	10.6	1	52.4	9.39	2.6
MADRL		16.3	7.23	1.8	26.8	16.0	4.7	51.1	25.9	9.5	19.2	7.86	1.8	31.3	18.1	4.7	58.3	21.1	9.5
DeepMDV (AM, G)		16.2	6.57	0.4	25.3	9.52	1.7	45.4	11.8	4.2	18.5	3.93	0.4	27.8	4.90	1.7	50.5	5.42	4.2
DeepMDV (LKH3, G)		16.0	5.26	1	24.8	7.35	2.4	44.1	8.62	5.7	18.3	2.80	1	27.4	3.39	2.4	49.3	2.92	5.7
DeepMDV (LKH3, G, P)		15.8	3.94	1	24.5	6.06	2.4	43.2	6.40	5.7	18.2	2.24	1	27.2	2.64	2.4	49.0	2.29	5.7
HGS	4	15.1^∗	0.00	20	22.4^∗	0.00	60	39.8^∗	0.00	180	17.3^∗	0.00	20	25.8^∗	0.00	60	46.5^∗	0.00	180
Cluster + AM (bs30)		17.1	13.2	0.2	28.3	26.3	0.6	56.4	41.7	1.4	19.2	11.0	0.2	34.4	33.3	0.6	61.4	32.0	1.4
Cluster + POMO		16.4	8.61	0.2	25.4	13.4	0.7	47.3	18.8	1.7	19.7	13.9	0.2	28.6	10.9	0.7	55.7	19.8	1.7
Cluster + GLOP		18.1	19.9	0.4	25.7	14.7	1	45.2	13.56	2.6	20.1	16.2	0.4	29.1	12.8	1	52.1	12.0	2.6
MADRL		16.7	10.6	1.9	27.6	23.2	4.8	53.2	33.7	9.7	18.7	8.09	1.9	30.6	18.6	4.8	56.4	21.2	9.7
DeepMDV (AM, G)		15.8	4.63	0.4	24.3	8.48	1.7	43.1	8.29	4.2	18.0	4.04	0.4	26.7	3.48	1.7	49.2	5.80	4.2
DeepMDV (LKH3, G)		15.7	3.97	1	23.8	6.25	2.4	42.0	5.52	5.7	17.8	2.89	1	26.4	2.32	2.4	48.2	3.65	5.7
DeepMDV (LKH3, G, P)		15.6	3.31	1	23.6	5.35	2.4	41.6	4.52	5.7	17.7	2.31	1	26.2	1.55	2.4	47.9	3.01	5.7