## Yan Zhang* , Tengyu Wu and Xiaoyue Ding## |

Distribution point | Date | Distribution vehicle | Distribution distance (100 km) | Load rate (%) | Volume rate (%) | Customer satisfaction | |||||
---|---|---|---|---|---|---|---|---|---|---|---|

Before | After | Before | After | Before | After | Before | After | Before | After | ||

11 | Jan 6 | 5.00 | 3.00 | 1.73 | 1.63 | 74 | 87 | 73 | 85 | 2.28 | 2.27 |

11 | Jan 7 | 5.00 | 3.00 | 1.88 | 1.66 | 75 | 90 | 73 | 85 | 2.36 | 2.29 |

11 | Jan 11 | 5.00 | 3.00 | 1.90 | 1.83 | 77 | 88 | 74 | 84 | 2.41 | 2.31 |

11 | Jan 12 | 5.00 | 3.00 | 1.67 | 1.66 | 78 | 92 | 77 | 90 | 2.36 | 2.41 |

11 | Jan 14 | 5.00 | 3.00 | 1.94 | 1.73 | 78 | 91 | 75 | 88 | 2.54 | 2.36 |

11 | Jan 15 | 5.00 | 3.00 | 1.86 | 1.65 | 77 | 91 | 76 | 91 | 2.47 | 2.30 |

18 | Jan 7 | 6.00 | 3.00 | 2.10 | 1.91 | 73 | 97 | 70 | 93 | 2.61 | 2.58 |

18 | Jan 11 | 6.00 | 3.00 | 1.87 | 2.22 | 69 | 90 | 66 | 85 | 2.46 | 2.40 |

18 | Jan 12 | 6.00 | 3.00 | 1.92 | 1.89 | 70 | 92 | 67 | 87 | 2.57 | 2.43 |

18 | Jan 13 | 6.00 | 3.00 | 1.87 | 1.87 | 72 | 92 | 70 | 90 | 2.49 | 2.53 |

18 | Jan 14 | 6.00 | 3.00 | 1.92 | 2.09 | 67 | 94 | 66 | 90 | 2.49 | 2.45 |

18 | Jan 15 | 6.00 | 3.00 | 1.84 | 2.04 | 68 | 93 | 67 | 88 | 2.42 | 2.43 |

18 | Jan 17 | 6.00 | 3.00 | 2.10 | 1.60 | 72 | 97 | 71 | 96 | 2.71 | 2.55 |

7 | Jan 7 | 5.00 | 3.00 | 1.94 | 1.68 | 79 | 91 | 79 | 95 | 2.31 | 2.45 |

7 | Jan 8 | 5.00 | 3.00 | 1.83 | 1.98 | 62 | 85 | 65 | 90 | 2.29 | 2.31 |

7 | Jan 9 | 5.00 | 3.00 | 1.82 | 1.60 | 78 | 92 | 75 | 88 | 2.35 | 2.40 |

7 | Jan 11 | 5.00 | 3.00 | 1.86 | 1.69 | 78 | 93 | 75 | 87 | 2.40 | 2.44 |

7 | Jan 12 | 5.00 | 3.00 | 1.92 | 1.75 | 81 | 91 | 78 | 89 | 2.34 | 2.41 |

7 | Jan 13 | 5.00 | 3.00 | 1.91 | 1.98 | 66 | 92 | 64 | 86 | 2.32 | 2.36 |

7 | Jan 14 | 5.00 | 3.00 | 1.92 | 1.92 | 66 | 92 | 63 | 87 | 2.32 | 2.33 |

7 | Jan 15 | 5.00 | 3.00 | 1.94 | 1.85 | 79 | 87 | 79 | 79 | 2.33 | 2.29 |

Mean range | [TeX:] $$\downarrow 2.33$$ | [TeX:] $$\downarrow 7\%$$ | [TeX:] $$\uparrow 18\%$$ | [TeX:] $$\uparrow 16\%$$ | [TeX:] $$\downarrow 2\%$$ |

The changing trend of the total message with postage algorithm iterative process is shown in Fig. 5. In the Fig. 5, the black point line presents the BPSO-SA algorithm postage objective function changing with the number of iterations situation. We can see from the chart, the BPSO-SA optimization algorithm convergence speed is faster than other algorithms and can obtain higher total postage.

The computational complexity of the BPSO-SA algorithm is also better than other three algorithms. It can be seen from Fig. 5, to reach the same total postage 6000, the BPSO-SA algorithm only needs 57 iterations, the SA algorithm needs 203 iterations, the BPSO algorithm needs 716 iterations and the GA algorithm cannot reach 6000. So, the BPSO-SA is more efficient than other three algorithms.

(4) Table 2 shows that the simulation results of the BPSO-SA algorithm are the best of the four algorithms (BPSO-SA, GA, BPSO, and SA) in terms of total mass, total postage, and full load rate under the same conditions. The average value of total mass fluctuates around 598.8, the maximum value is fixed at 600 and the minimum value is maintained at 594; the average value of total postage gradually decreases, the maximum value increases abruptly to 6199 and the minimum value decreases to 5980; the average value of full load rate gradually increases to 99.1%, the maximum value is fixed at 99.8% and the minimum value decreases to 97.0%.

Table 2.

Algorithm | Total mass | Total postage | Full-load ratio (%) | |||||||
---|---|---|---|---|---|---|---|---|---|---|

Avg | Max | Min | Avg | Max | Min | Avg | Max | Min | ||

10 | SA | 597.60 | 600.00 | 587.00 | 5847.20 | 5930.00 | 5749.00 | 98.6 | 99.8 | 95.7 |

BPSO | 597.40 | 600.00 | 588.00 | 6084.40 | 6140.00 | 6008.00 | 98.6 | 99.5 | 97.3 | |

GA | 593.80 | 600.00 | 581.00 | 5900.40 | 5998.00 | 5804.00 | 94.3 | 96.3 | 91.5 | |

BPSO-SA | 598.80 | 600.00 | 597.00 | 6085.40 | 6162.00 | 6010.00 | 99.1 | 99.8 | 97.8 | |

20 | SA | 596.15 | 600.00 | 584.00 | 5858.70 | 5943.00 | 5745.00 | 98.9 | 99.8 | 95.7 |

BPSO | 597.70 | 600.00 | 588.00 | 6072.90 | 6175.00 | 5989.00 | 98.3 | 99.8 | 96.2 | |

GA | 594.35 | 600.00 | 581.00 | 5912.15 | 6033.00 | 5799.00 | 95.1 | 98.3 | 91.5 | |

BPSO-SA | 598.70 | 600.00 | 595.00 | 6076.30 | 6162.00 | 5980.00 | 99.1 | 99.8 | 97.0 | |

40 | SA | 596.08 | 600.00 | 584.00 | 5863.00 | 5993.00 | 5624.00 | 98.9 | 99.8 | 94.5 |

BPSO | 597.45 | 600.00 | 588.00 | 6068.60 | 6175.00 | 5977.00 | 98.5 | 99.8 | 95.3 | |

GA | 594.13 | 600.00 | 570.00 | 5924.10 | 6070.00 | 5724.00 | 94.8 | 99.5 | 88.3 | |

BPSO-SA | 598.78 | 600.00 | 594.00 | 6073.40 | 6162.00 | 5980.00 | 99.2 | 99.8 | 97.0 | |

60 | SA | 596.10 | 600.00 | 575.00 | 5847.97 | 6011.00 | 5624.00 | 98.9 | 99.8 | 94.5 |

BPSO | 597.82 | 600.00 | 588.00 | 6068.46 | 6175.00 | 5977.00 | 98.5 | 99.8 | 95.3 | |

GA | 593.64 | 600.00 | 570.00 | 5933.75 | 6128.00 | 5724.00 | 94.6 | 99.8 | 88.3 | |

BPSO-SA | 598.84 | 600.00 | 594.00 | 6073.00 | 6199.00 | 5980.00 | 99.3 | 99.8 | 97.0 |

The existing algorithms for solving the logistics knapsack problem are easy to fall into local optimum. The BPSO algorithm has a good global search ability. The SA algorithm has an excellent local search ability. The proposed integrated optimization algorithm that combined the above 2 algorithms can avoid local optimum. The experimental results show that the proposed algorithm can effectively optimize the backpack problem by reducing the number of distribution vehicles and distance. The experimental results also show that, by comparing the four algorithms (BPSO_SA, GA, BPSO, and SA), the integrated algorithm (BPSO_SA) has the best performance in terms of full load rate, total postage and total mass.

Due to the limitations of the experimental conditions, the research in this paper is mainly carried out on the basis of the data generated by the simulation model. In the next step of research, the actual logistics data will be used for experiments to verify the validity of the proposed algorithm.

She received her B.E. degree in international journalism from Sichuan International Studies University in 2004, M.S. and Ph.D. degree in logistics from Inha University, South Korea in 2007 and 2018, respectively. She is currently a lecturer in School of Management, Chongqing University of Posts and Telecommunications, Chongqing, China. Her research interests include logistics management and logistics system optimization.

He received his B.E. degree in engineering management from Xi’an Jiaotong Uni-versity in 2006, M.S. in Xi’an University of Technology, Ph.D. degree in Xi’an Jiaotong University. He is currently a lecturer in School of Modern Post, Chongqing University of Posts and Telecommunications, Chongqing, China. His research interests include logistics management and routing optimization.

She received B.E. degree in Internet of Things Engineering from Chongqing Uni-versity of Posts and Telecommunications in 2020. Since September 2020, she is with the School of Automation, Chongqing University of Posts and Telecommunications, Chongqing, China as a M.S. candidate. Her current research interests include internet of vehicle and video transmission.

- 1 J. H. Drake, M. Hyde, K. Ibrahim, and E. Ozcan, "A genetic programming hyper-heuristic for the multidimensional knapsack problem,"
*Kybernetes*, vol. 43, no. 9/10, pp. 1500-1511, 2014.doi:[[[10.1108/k-09-2013-0201]]] - 2 Z. Beheshti, S. M. Shamsuddin, and S. Hasan, "Memetic binary particle swarm optimization for discrete optimization problems,"
*Information Sciences*, vol. 299, pp. 58-84, 2015.doi:[[[10.1016/j.ins.2014.12.016]]] - 3 F. Glover, "Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems,"
*European Journal of Operational Research*, vol. 230, no. 2, pp. 212-225, 2013.doi:[[[10.1016/j.ejor.2013.04.010]]] - 4 I. B. Mansour and I. Alaya, "Indicator based ant colony optimization for multi-objective knapsack problem,"
*Procedia Computer Science*, vol. 60, pp. 448-457, 2015.doi:[[[10.1016/j.procs.2015.08.165]]] - 5 S. C. Leung, D. Zhang, C. Zhou, and T. Wu, "A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem," Computers & Operations Research, vol. 39, no. 1, pp. 64-73, 2012.doi:[[[10.1016/j.cor.2010.10.022]]]
- 6 B. Haddar, M. Khemakhem, H. Rhimi, and H. Chabchoub, "A quantum particle swarm optimization for the 0–1 generalized knapsack sharing problem,"
*Natural Computing*, vol. 15, no. 1, pp. 153-164, 2016.doi:[[[10.1007/s11047-014-9470-5]]] - 7 C. Sachdeva and S. Goel, "An improved approach for solving 0/1 knapsack problem in polynomial time using genetic algorithms," in Proceedings of International Conference on Recent Advances and Innovations in Engineering (ICRAIE), Jaipur, India, 2014, pp. 1-4.doi:[[[10.1109/icraie.2014.6909284]]]
- 8 R. Merkle and M. Hellman, "Hiding information and signatures in trapdoor knapsacks,"
*IEEE Transactions on Information Theory*, vol. 24, no. 5, pp. 525-530, 1978.doi:[[[10.1109/tit.1978.1055927]]] - 9 Y . Li, Y . He, H. Li, X. Guo, and Z. Li, "A binary particle swarm optimization for solving the bounded knapsack problem,"
*in Computational Intelligence and Intelligent Systems*. Singapore: Springer, 2018, pp. 50-60.custom:[[[-]]] - 10 Y . He, H. Xie, T. L. Wong, and X. Wang, "A novel binary artificial bee colony algorithm for the set-union knapsack problem,"
*Future Generation Computer Systems*, vol. 78, pp. 77-86, 2018.doi:[[[10.1016/j.future.2017.05.044]]] - 11 Y . Zhang, X. Y . Wu, and O. K. Kwon, "Research on Kruskal crossover genetic algorithm for multi-objective logistics distribution path optimization,"
*International Journal of Multimedia and Ubiquitous Engineering*, vol. 10, no. 8, pp. 367-378, 2015.doi:[[[10.14257/ijmue.2015.10.8.36]]]