یک روش ابتکاری برای حل مشکل مسیریابی موجودی همراه با پنجره زمانی

This paper is to resolve the VRPTW and the inventory control decision problem simultaneously since both the vehicle routing decision with time windows and the inventory control decision affect each other and must be considered together. A mathematical model of inventory routing problem with time windows (IRPTW) is proposed. Since finding the optimal solution(s) for IRPTW is a NP-hard problem, this paper proposes a two-phase heuristic method. The first phase is to find the initial solution. The second phase is to improve the solution adopting the variable neighborhood tabu search (VNTS) selecting better neighborhood solutions, to obtain the optimal solution. Moreover, the proposed method was compared with three other heuristic methods. The experimental results indicate that the proposed method is better than the three other methods in terms of average supply chain cost (transportation cost, time window violation penalty cost and inventory cost).

The vehicle routing problem with time windows (VRPTW), which involves assigning a fleet of limited capacity vehicles to serve a set of customers without violating the capacity and time constraints, has been increasingly discussed in practice recently (Calvete et al., 2007, Kang et al., 2008 and Li et al., 2010). The VRPTW can be divided into two categories (Solomon, 1987): (1) soft-time windows and (2) hard-time windows. Since the time constraint of the vehicle routing problem with soft-time windows can flexibly reflect the real-world situation such as transportation problem (i.e. rush hour, car accident, shortage of drivers and vehicles), customers’ demand constraints, etc., it is adopted more often than that of the vehicle routing problem with hard-time windows (Cheng and Wang, 2009, Hashimoto et al., 2008 and Nagata and Braysy, 2009). Hence, it is adopted and discussed later in this paper. In the past, the resolution of VRPTW is based on the minimal cost criterion (including transportation cost and time window violation penalty cost) without considering the inventory cost (Figliozzi, 2010 and Hashimoto et al., 2008). However, when only one factor is accessed and minimized, the costs of other factors are increased (Moin & Salhi, 2007). For example, if the vehicle routing decision problem with time windows for suppliers is considered and the inventory control decision problem for retailers is neglected, the vehicle routing decision can be effectively made and however the inventory control decision cannot, causing suppliers not be able to reduce the supply chain cost (transportation cost, time window violation penalty cost and inventory cost) effectively. In contrast, if only the inventory control decision problem for retailers is considered and the vehicle routing decision problem with time windows for suppliers is ignored, the transportation and time window violation penalty cost would increase since the vehicle routing decision cannot be effectively made. Hence, the supply chain cost would increase. So the vehicle routing decision problem with time windows for suppliers and the inventory control decision problem for retailers need to be considered simultaneously in order to find the minimal supply chain cost. The inventory routing problem with time windows (IRPTW) considering inventory and routing decisions simultaneously has gained attentions since the vendor-managed inventory (VMI) strategy was adopted in practice (The applications of IRPTW include household care industry (P&G), computer equipment industry (Acer), beverage industry (Hey Song Corporation, the most famous beverage production company in Taiwan), etc. Actually, a lot of applications worldwide in different supply chains including production companies and retailers have already been reported.) (Andersson et al., 2010 and Moin and Salhi, 2007). However, the IRPTW is rarely discussed in literature. Hence, the purpose of this paper is to resolve the inventory routing problem with time windows (IRPTW) so that the supply chain cost can be decreased. Since IRPTW is a NP-hard problem (VRPTW is an NP-hard problem (Savelsbergh, 1985). IRPTW is more complex than VRPTW. Hence, IRPTW is also an NP-hard problem), a heuristic method will be adopted to resolve this problem. However, there is no heuristic method proposed for the IRPTW until now. Since the problem structure of IRPTW is similar to that of VRPTW. Hence, heuristic methods used in VRPTW are reviewed in the following. Taillard, Badeau, Gendreau, Guertin, and Potvin (1997) adopted a two-phase method to resolve the VRPTW. The random insertion method is used to obtain the initial solution. Then the tabu search method, adopting cross-exchange and or-opt neighborhood search strategies, is used to improve the initial solution. Park (2001) adopted a hybrid genetic algorithm to resolve the VRPTW. Tan, Lee, Zhu, and Ou (2001) investigated three methods: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) to resolve the VRPTW. The results show TS is better than SA and GA. Ioannou, Kritikos, and Prastacos (2003) adopted the nearest-neighbor method to resolve the VRPTW. Ichoua, Gendreau, and Potvin (2003) adopted a parallel tabu search method to resolve the VRPTW. The insertion method is used to obtain the initial solution. The cross-exchange neighborhood search strategy is used to improve the initial solution. Lau, Sim, and Teo (2003) adopted a two-phase method to resolve the VRPTW. The first phase is to find the initial solution. The second phase is to improve the initial solution using the tabu search method adopting the k-opt neighborhood search strategy. Olli (2003) adopted a variable neighborhood search method to resolve the VRPTW. Chen, Hsueh, and Chang (2006) adopted the insertion method to resolve the real-time VRPTW. Hashimoto et al. (2008) proposed a heuristic method adopting time dependent concept to resolve the VRPTW. 2-opt∗, cross-exchange and or-opt neighborhood search strategies are adopted in this method. Kang et al. (2008) adopted the tabu search method to resolve the VRPTW. The neighborhood search strategy is based on the route-perturb and route-improvement method. Fu, Eglese, and Li (2008) adopted the tabu search method to resolve the VRPTW. Figliozzi (2010) adopted an iterative route construction and improvement algorithm to resolve the VRPTW. Nagata and Braysy (2009) adopted a heuristic, insertion and guided local search strategies, to resolve the VRPTW. Li et al. (2010) adopted the tabu search to resolve the VRPTW with stochastic travel and service times. Cheng and Wang (2009) adopted a decomposition technique and a genetic algorithm to resolve the VRPTW. In this paper, a mathematical model for the IRPTW is proposed. Since finding the optimal solution for this model is an NP problem, a two-phase heuristic method is proposed for the IRPTW. The first phase is to find a better initial solution based on the construction approach. The second phase is to improve the initial solution based on the variable neighborhood tabu search (VNTS), tabu search adopting different neighborhood search strategies, to find the optimal solution for the IRPTW effectively and efficiently. The reason for choosing the hybrid heuristic approach is to overcome the drawbacks of variable neighborhood search (VNS) and tabu search (TS), two well-known methods to resolve the IRPTW. In addition, the hybrid method can take advantage of VNS and TS to improve search effectiveness and efficiency.

In this paper, we have developed an effective and efficient heuristic method to resolve the IRPTW. The proposed heuristic method is better than three other heuristic methods based on the minimal cost criterion in terms of average cost. In addition, the ratio for cost structure and the vehicle capacity influence the average cost. When the ratio for cost structure is from low to high or the vehicle capacity decreases, the average cost increases. Due to the limitations of this paper, some factors such as multiple products, different vehicle fleet, etc. are not considered. So considering these factors would help the inventory routing decision with time windows made more realistically.