Discrete firefly algorithm with compound neighborhoodsfor asymmetricmulti-depot vehicle routing problem inthe maintenance of

farm machinery 

       Jian Li^a*, Tingting Li^a, Yugang Yu^b*, Zhaotong Zhang^a, 

Panos M. Pardalos^c, Yi Zhang^a, Yunfeng Ma^d

^a College of Engineering, Nanjing Agricultural University, P.O. Box 8, 40 Dianjiangtai Road, Pukou district, Nanjing 210031, China, lijianzh@njau.edu.cn (Li, J), zzt5576@njau.edu.cn (Zhang, Z)

^bSchool of Management, University of Science and Technology of China, Hefei 230026, China, ygyu@ustc.edu.cn

^c Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA, pardalos@ise.ufl.edu

^dSchool of Management, Wuhan University of Science & Technology, Wuhan 430081, China, mayunfeng@wust.edu.cn

* represents the co-corresponding authors

Abstract

We introduce a new variant of the vehicle routing problem, that is, the asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery. When providing door-to-door service for farm machinery maintenance, there exists not only node service, (e.g., part replacement), but also directed arc service, (e.g., pulling the breakdown farm machinery from the farm location to the specified maintenance station). In the problem, there are multiple constraints, including the customer's time window, maximum repairman working duration, fleet size, and vehicle capacity, etc. A mathematical programming model is formulated with the minimum total costs by transforming the problem into the asymmetric multi-depot vehicle routing problem with time windows. Discrete firefly algorithm with compound neighborhoods, presenting new neighborhood methods, is proposed to solve it. New procedures to evaluate the duration infeasibilityare suggested with the reduced additional computational complexity. Computational results demonstrate that the proposed approach performs better than CPLEX solver, especially for large designed instances. Moreover, the proposed approach is superior to the other algorithms on solving benchmark instances of multi-depot vehicle routing problem with time windows. This study can provide decision support to door-to-door service for the maintenance of farm machinery.  

Keywords:asymmetric vehicle routing problem; multi-depot; firefly algorithm; compound neighborhoods; maintenance of farm machinery 

1 Introduction

       In thedoor-to-door maintenance service of farm machinery(DMSFM) procedure, clients make phone calls to the maintenance information center. Staff in the center respond and record client locations, vehicle information, and fault causes, as well as appointments for when repairmen can offer service. According to the customers’ time windows, repairmen are assigned to be dispatched to client locations with tools and replacement parts uniformly onthe following day. For example, LOVOL, a famous farm machinery company in China, running large farm implements and household farm machinery, adopts this mode to offer after-sale maintenance service to customers. The demand fordoor-to-door servicegradually rises with the gradual increase of the rural aging population and application of the remote diagnosis technology. 

Inappropriate arrangements are easy to generate by assigning the repair vehicle manually because of the constraints, such as maximum working duration, vehicle capacity, fleet size, and customers’ time windows, especially the numerous maintenance demands during a busy farming season. Inappropriate arrangements not only reduce customer satisfaction but also increase costs.