Article Preview
TopIntroduction
Spare part is the core element of fault repair and maintenance services. Due to the direct interaction with users in the process of spare part allocation, efficient distribution of spare parts has become one of the key factors to improve the level of repair and maintenance services. Currently, most manufacturers of hobbing machines lack planning for spare part distribution, which leads to the poor customers’ satisfaction and the high delivery costs. As the core issue in spare part distribution, establishing a reasonable distribution model and developing efficient vehicle scheduling scheme play a key role in improving the efficiency of spare part allocation.
Proposed by Dantzig and Ramser in 1959, VSP (Vehicle Schedule Problem), which aims at seeking the best vehicle route to service a number of customers under certain conditions to achieve objectives such as the shortest time and distance or the lowest cost (ZHAO, 2009a), is a typical NP-hard problem in combinatorial optimization (Golden, 1984). Classic vehicle scheduling problem only takes the constraint of vehicle capacity into account. With the diversification of user demands and the expansion of scale of VSP, the study about VSP has been extended to more aspects, such as the gradual upgrading from single-objective optimization problem to multi-objective optimization, taking time windows as constraints or considering more different types of vehicles. For example, real-time vehicle rerouting problems with time windows request one or more vehicles need to be rerouted, in real-time, to perform uninitiated services (Li, Mirchandani, & Borenstein, 2009b). For vehicle routing problem with time windows, an iterated local search algorithm by allowing both traveling times and traveling costs to be time-dependent functions is applied to determine routes of the vehicles (Hashimoto, Yagiura, & Ibaraki, 2008a). In terms of algorithms of VSP, integer linear program (MOU, 2012a; ZHANG, 2013a) and dynamic programming (Prins, Lacomme, & Prodhon, 2014a) were applied in solving simple and small-scale VSP at the beginning of research. Considering the complexity and diversity of VSP, accurate algorithm was no longer suitable to solve VSP with more than 50 demand points (Golden, Wasil, Kelly, & Chao, 1998). Then the research of algorithm was concentrated on heuristic algorithm. The savings algorithm, proposed by Clark, could be applied to solve the VSP problem and obtain the approximate optimal solution efficiently, without taking the influence of time on the results into consideration (QI, LU, & SUN, 2010). For specific VSP problems, modified savings algorithm has been used and the savings method can also be implemented on microcomputers (Paessens, 1988). For stochastic vehicle routing problem, in which the actual customer demand is not known with certainty when the vehicle routes are designed, the modified savings algorithm was used to illustrate the effects of route failure on the expected cost of a route (Dror & Trudeau, 1986). Scanning algorithm was widely used despite the complex calculation (GUO, YANG, YU, & LIAO, 2012b). Besides, other classic heuristic algorithms were also applied to solve VSP, such as 2-Approximation algorithms (Karuno & Nagamochi, 2003; Nagamochi & Ohnishi, 2008b), greedy algorithm (Brecklinghaus & Hougardy, 2015a), genetic algorithm (Anbuudayasankar, Ganesh, Koh, & Ducq, 2012c), ant colony optimization (Chan, Shekhar, & Tiwari, 2014b; Cheng, Leung, & Li, 2015b) and tabu search (GE, WANG, & DENG, 2013b).