A CONSTRAINT PROGRAMMING HEURISTIC FOR A HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH SPLIT DELIVERIES

Figures & data

FIGURE 1 Flow diagram of the proposed algorithm.

TABLE 1 Notation Used in Model SC

TABLE 2 Notation Used in Model VA

TABLE 3 Additional Notation Used in Model CPM

TABLE 4 Data Belonging to Test Instances

		A		B		C		D		E		F
Test instance	Number of nodes	Capv	Costv	Capv	Costv	Capv	Costv	Capv	Costv	Capv	Costv	Capv	Costv
3	20	20	20	30	35	40	50	70	120	120	225
4	20	60	1000	80	1500	150	3000
5	20	20	20	30	35	40	50	70	120	120	225
6	20	60	1000	80	1500	150	3000
13	50	20	20	30	35	40	50	70	120	120	225	200	400
14	50	120	100	160	1500	300	3500
15	50	50	100	100	250	160	450
16	50	40	100	80	200	140	400
17	75	50	25	120	80	200	150	350	320
18	75	20	10	50	35	100	100	150	180	250	400	400	800
19	100	100	500	200	1200	300	2100
20	100	60	100	140	300	200	500

TABLE 5 Performance of the Proposed Algorithm in [151984Golden et al.] Test Problems

					Proposed algorithm
Problem no.	Number of nodes	Taillard 1999	Gendreau et al. 1999	Choi and Tcha 2007	Cost	Time	Deviation in cost (%)
3	20	961.03	961.03	961.03	983.1	52	2.24
4	20	6437.3	6437.33	6437.3	6437.33	32	0.00
5	20	1008.59	1007.05	1007.05	1052.15	70	4.29
6	20	6516.5	6516.47	6516.5	6516.47	131	0.00
13	50	2413.78	2408.41	2406.36	2440.78	113	1.41
14	50	9119.03	9119.03	9119.03	9138.25	374	0.21
15	50	2586.37	2586.37	2586.37	2620.54	200	1.30
16	50	2741.5	2741.5	2720.43	2746.3	43	0.94
17	75	1747.24	1749.5	1744.83	1783.33	340	2.16
18	75	2373.63	2381.43	2371.49	2394.16	442	0.95
19	100	8661.81	8675.16	8664.29	8734.35	453	0.83
20	100	4047.55	4086.76	4039.49	4139.8	261	2.42

TABLE 6 Performance of the Proposed Algorithm on Solomon Test Problems

			Proposed algorithm
Problem no.	Number of nodes	Best known in literature	Cost	Deviation in cost (%)	Solution time (sec)
C101	100	828.9	828.9	0.00	< = 1
C102	100	828.9	828.9	0.00	4
C103	100	828.06	828.9	0.10	27
C104	100	824.8	828.9	0.49	89
C105	100	828.9	828.9	0.00	< = 1
C106	100	828.9	828.9	0.00	< = 1
C107	100	828.9	828.9	0.00	< = 1
C108	100	828.9	828.9	0.00	4
C109	100	828.9	828.9	0.00	9
C201	100	591.6	591.6	0.00	81
C202	100	591.6	591.6	0.00	484
C203	100	591.2	591.2	0.00	215
C204	100	590.6	591.6	0.17	1024
C205	100	588.9	591.6	0.46	78
C206	100	588.5	591.6	0.52	96
C207	100	588.3	591.6	0.56	85
C208	100	588.3	591.6	0.56	561

TABLE 7 Performance of the Proposed Algorithm on [151984Golden et al.] Test Problems Under Split Delivery Assumption

			Proposed algorithm
Problem no.	Number of nodes	Best known ∗ in literature	Cost	Deviation in cost (%)	Solution time (sec)
3	20	961.03	970.53	0.98	104
4	20	6437.3	6421.88	−0.24	45
5	20	1008.59	998.74	−0.83	84
6	20	6516.5	6514.09	−0.04	137
13	50	2413.78	2440.78	1.41	146
14	50	2406.36	9138.25	0.21	412
15	50	2586.37	2616.11	1.14	298
16	50	2720.43	2719.89	−0.02	302
17	75	1744.83	1783.33	2.16	317
18	75	2371.49	2394.16	0.95	486
19	100	8661.81	8722.49	0.67	506
20	100	4039.49	4130.48	2.20	396

FIGURE 2 Demand points of the retail chain store.

TABLE 8 Data Belonging to Vehicles Available

Vehicle	Capacity	Fixed cost
1	11,484	1148.4
2	11,144	1114.4
3	14,314	1431.4
4	10,514	1051.4
5	9980	998
6	11,824	1182.4
7	10,514	1051.4
8	15,724	1572.4
9	12,000	1200

TABLE 9 Comparison of Different Distribution Strategies and the Current Performance of the Firm

	No. of vehicles allocated	Fixed cost (TL)	Traveling cost (TL)	Total cost (TL)	Solution time (sec)	Improvement (%)
	5	5362	3908	9270	–	–
Nonsplit delivery strategy	4	4311	3792	8103	36	12.59
Split delivery strategy	4	4311	3787	8098	73	12.64

FIGURE 3 Routes of (a) nonsplit delivery distribution strategy and (b) split delivery distribution strategy.