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

This paper introduces the vehicle routing problem with soft time windows (VRPSTW) in which problem definition differs from ones previously defined in literature. Branch-and-price approach is employed, resulting in a set partitioning master problem and its new subproblem. Novel techniques are consequently developed to solve this new subproblem. Experimental results report the comparisons of these solution techniques under the branch-and-price framework. The VRPSTW solutions have further been compared to the state-of-the-art literature, signifying the superiority of the VRPSTW on this issue.

Much attention has been paid to urban freight transport (commodity movement), which is a significant issue in urban planning. As urban freight transport can generate some serious problems in urban areas and it mainly affects the profit of logistics distributors, effective tools for optimizing urban freight transport are thus required (Ando and Taniguchi, 2006, Taniguchi and Kakimoto, 2003 and Taniguchi et al., 1999). One of such tools is the Vehicle Routing Problem (VRP). The aim of the VRP is to design an optimum cost set of delivery routes to supply all customer requirements subject to side constraints (Laporte, 1992 and Laporte, 2009). Since the VRP has emerged in the literature, various extensions to the basic VRP have been proposed in order to represent different characteristics of practical problems. An important extension is the VRP under time window constraints that involves additional time requirements from customers. Each customer, indexed by i , requests to be serviced by a single delivery vehicle at his location within his specified time window [ai , bi ]. The problem addressed here is the so-called VRP with hard time windows (VRPHTW). A vehicle can arrive at customer location before time window, but it needs to wait at no cost until the beginning of time window to start service. Any visit and service after time window is infeasible ( Braysy and Gendreau, 2005a and Braysy and Gendreau, 2005b). It is however obvious that the VRPHTW has weaknesses when applying it to real-life situations, that is, managing vehicles to service all customers within time windows is very difficult in practice, and it is likely to receive very high costs due to use of many vehicles. To avoid these drawbacks, Qureshi et al., 2009 and Qureshi et al., 2010 partially relaxed time window constraints by introducing time-dependent late arrival penalties to the problem. The problem is then described as the VRP with semi-soft time windows (VRPSSTW). In the VRPSSTW, a vehicle is allowed to visit and serve a customer later than his time window, however a time-dependent late arrival penalty must be taken into consideration if the delayed service occurs. The vehicle still has to wait to start service until ai without cost if it arrives too early. Qureshi et al., 2009 and Qureshi et al., 2010 also introduced the maximum allowable late arrival time at each customer to be visited (represented by View the MathML sourcebi′) by considering a trade-off between fixed vehicle cost and late arrival penalty. The numerical experiments reported in Qureshi et al. (2009) show that the VRPSSTW can decrease number of vehicles used in the solution (as compared to the VRPHTW). The overall costs could consequently be reduced. In addition, total waiting time of vehicles, although not considered as main objective, is also reduced. Nevertheless, there still exists a significant amount of waiting time in the VRPSSTW solution. This amount of waiting time is meaningful in practice. First of all, waiting time implies non-profitable time of logistics distributor and firm’s resources are also being underutilized. Spending too long time in waiting not only causes the loss of opportunity to generate more profits but also incurs extra costs such as vehicle/labor operating cost, maintenance cost, and parking fee. Secondly, it might contribute to traffic and environmental related problems such as traffic congestion due to waiting at inappropriate place, and air pollution if the vehicle waits in engine on state. Apparently, the VRPSSTW could cope with the drawbacks of the VRPHTW, yet they are addressed only partially. Both the VRPHTW and the VRPSSTW still generate significant amount of waiting time of vehicles. Therefore, in addition to optimization of total routing costs, our aim is to also simultaneously minimize total waiting time of all vehicles. The problem considered in this paper is called the VRP with soft time windows (VRPSTW). Early arrival penalties, in addition to late arrival penalties, are also introduced to the problem. Indeed, a vehicle is possible to arrive and service after time window with taking late arrival penalty into account. On the other hand, if the vehicle arrives early, it must wait to begin the service until ai with taking early arrival penalty (or waiting cost) into account. However, the vehicle is not permitted to wait if it arrives within time window or later so that the service must start immediately. This matter is important in the proposed VRPSTW characteristics since the objective is to minimize total waiting time as well as total routing costs (and the corresponding late arrival penalties). For the sake of both objectives, any unnecessary waiting, i.e. whether within time window or later, is definitely not optimal and it needs to be avoided. In general, types (such as linear and non-linear) of penalties might vary from one customer to another, depending on importance, priority, and criticality. However, in this paper, both early and late arrival penalties are assumed to be linearly proportional to the early and late arrival time of vehicles, respectively. To prevent too long waiting time and delayed time which are impractical, the maximum limits of early arrival time and late arrival time at each customer View the MathML source[ai′,bi′] are also imposed. Therefore, it becomes infeasible to visit a customer beyond maximum limits of either early arrival time or late arrival time. Fig. 1 shows time-dependent arrival penalty functions of the three variants of the VRP under time window constraints (i.e. the VRPHTW, the VRPSSTW and the VRPSTW, respectively).In combinatorial optimization problem perspective, the VRPSTW is much harder to be solved to optimality than the VRPHTW and the VRPSSTW. The main difficulty of solving the VRPSTW is that time-dependent arrival penalties, i.e. both early and late arrival penalties, are considered. Because time-dependent arrival penalty function is not a non-decreasing function, consequently the cost function along a route traversed by a vehicle is also not a non-decreasing function as well. This makes the problem more complicated. Besides, due to taking early arrival penalty into account, the vehicle does not necessarily depart as early as possible. Departure time from depot of each vehicle must therefore optimally be determined. Through the years, a great number of research papers has been dedicated to the VRPHTW (see e.g. Alvarenga et al., 2007, Azi et al., 2007, Azi et al., 2010, Baldacci et al., 2011, Fisher et al., 1997, Kallehauge et al., 2006, Kohl and Madsen, 1997 and Potvin and Rousseau, 1993). On contrary, a few cases have studied on the soft time window variants. These include the work of Balakrishnan (1993), where servicing a customer before or after time window is possible with taking appropriate penalties. However, the vehicle could decide to wait (not more than a maximum limit) without penalty instead of premature service with early penalty due to economical reasons or exceeding the allowed maximum penalty. Simple constructive heuristics were used in his work to provide the solution to the corresponding problem. Some effective heuristics and metaheuristics such as nearest-neighbor heuristic (Ioannou et al., 2003), tabu search (Chiang and Russell, 2004), and local search approaches (Hashimoto et al., 2006 and Ibaraki et al., 2005) were further exploited to solve similar problems. The VRPSTW of Gendreau et al. (1999) and Taillard et al. (1997) allow late services with late penalties, while waiting of vehicles could be possible at no cost in case of early arrival. Their soft time window settings are implicitly equivalent to the VRPSSTW of Qureshi et al., 2009 and Qureshi et al., 2010, yet no maximum limitation on lateness at customer location, i.e. View the MathML sourcebi′, has properly been defined. Tabu search heuristics were proposed to solve the subject problems. More recently, Tagmouti et al., 2007 and Tagmouti et al., 2010 have presented, respectively, a column generation and a variable neighborhood descent heuristic approach for solving the winter gritting operations with time-dependent service costs (equivalent to penalties). In their problems, service costs are conditional to the timing of services, that is, service costs are paid according to either timely or untimely services; yet, service costs are sharply higher in case of untimely services. The vehicle is not permitted to wait elsewhere along the route. Tagmouti et al. (2011) have also developed a variable neighborhood heuristic for a dynamic version of their winter gritting problems in which service cost functions were uncertain due to weather updates. A column generation has also been adapted to the VRPSTW of Liberatore et al. (2011), where a penalty is paid whenever a customer is served beyond time window (early or late); it is however possible for each vehicle to wait at no cost at any time over its route, and no maximum limit of time window violation is defined so far. The work of Figliozzi (2010) is to develop an iterative route construction and route improvement procedure to efficiently solve the VRPSTW problems of Balakrishnan (1993) and Fu et al. (2008). The dynamic VRPSTW of Ferrucci et al. (2013) seeks to minimize total customer inconveniences (also equivalent to penalties). In their problem settings, each vehicle is forced to give service to each request as soon as possible during the assigned response time, i.e. the time window, whereas any service after the maximum allowed response time would involve high penalty, i.e. high inconvenience. To our best knowledge, however, all VRPSTW papers appearing in the literature are differently defined from ours, which could be described as follows: (1) The VRPSTW defined in this paper considers the case when the customers are not willing to be serviced before the start of time windows. It does not allow to service before the beginning of time window (ai ), i.e. a vehicle has to wait with early arrival penalty in case of early arrival. Note that the concerned early arrival penalty rather implies a waiting cost than a penalty to be paid due to premature service. (2) We limit the possible arrival time of the vehicle at each customer location within View the MathML source[ai′,bi′]; the values of View the MathML sourceai′ and View the MathML sourcebi′ are obtained by considering the trade-off between fixed vehicle costs and time-dependent arrival penalties (using Eqs. (1) and (2) defined in Section 4). Arrival beyond these limits is always infeasible. (3) All vehicles are not permitted to wait if they arrive within time windows or later so that the services must start immediately. Similarly, all vehicles need to leave as soon as the given services are completed. (4) The objective of our study is to develop the exact-based solution approaches, which could simultaneously minimize total routing costs and total waiting time of all routes.

This paper has introduced a new extension to the VRP under time window constraints based on a new definition of the VRPSTW. The VRPSTW, defined in this paper, is different from all existing ones in the literature. The objective behind the use of the new soft time window definition was to minimize total waiting time of all vehicles in addition to optimization of total routing costs. A new mixed integer three-index vehicle flow formulation has also been proposed for the VRPSTW based on the new soft time window definition. In addition to travel costs, the time-dependent arrival penalties (both early arrival and late arrival) and fixed vehicle costs were included to the objective function of the VRPSTW model. Once the vehicle arrives before the opening of time window, it needs waiting with taking early arrival penalty into account. Such early arrival penalty rather implies waiting cost and resource underutilized cost in practice. On the contrary, if the vehicle arrives later than time window, the service must be given to customer immediately at a late arrival penalty. The fixed vehicle utilization cost was also of importance for the purpose to demonstrate a trade-off between fixed cost of vehicle and time-dependent arrival penalties. This trade-off is also highly significant in practice. Furthermore, in the proposed VRPSTW model, maximum allowable violations of customer’s time windows were also introduced, which have been computed based on before-mentioned trade-offs. To optimally solve the proposed VRPSTW, a new branch-and-price approach was developed and employed. Though its application is quite restricted to small-sized and medium-sized instances, the exact-based branch-and-price approach is, in general, inevitable as its usage would identify the optimal solution to problem; whereas other solution approaches (such as heuristics) could not even express how close to the optimal solution their solutions are. The fundamental structure of the branch-and-price approach is to embed column generation algorithm into the branch-and-bound scheme. The column generation algorithm in turn is based on the decomposition of the VRPSTW, resulting in the set partitioning MP and a new SP, named as the ESPPRC-TAP. To tackle the ESPPRC-TAP, some complexities, which were directly received from the VRPSTW model, must particularly be considered. As the proposed VRPSTW differs in definition, use of the existing solution algorithms is not applicable for the ESPPRC-TAP. Therefore, two new exact-based techniques under labeling algorithm framework (the 1-SA and the 2-SA) were proposed to generate a set of elementarily feasible routes at the SP level. Two simple heuristics were also presented to combine with two exact-based techniques, so as to accelerate the SP solution algorithms. The resulting branch-and-price approach with four different SP solution techniques were evaluated on some instances of R1 and RC1 types from Solomon’s benchmark set. The obtained results indicated that the branch-and-price approach with the 2-SA along with heuristics (i.e. the resulting Heu-1&Heu-2&2-SA technique) is the most efficient technique among the ones described in this paper. The comparisons among the three variants of the VRP under time window constraints, i.e. the VRPHTW, the VRPSSTW, and the VRPSTW, on benchmark instances as well as on a practical instance were also provided. It was found that by accepting late deliveries with taking late arrival penalties into account, the number of vehicles used in the operation could be saved (occurred in both the VRPSSTW and the VRPSTW). Consequently, fixed vehicle utilization costs could be reduced, thus also leading to a decrease in the overall costs. Furthermore, by taking early arrival penalties into consideration (occurred only in the proposed VRPSTW), it was likely to receive less amount of waiting time. The total amount of waiting time of all solutions in the VRPSTW was significantly decreased as compared to the VRPHTW and the VRPSSTW solutions in our computational experiments. Even though visiting customers outside their time windows was penalized, yet the time-dependent arrival penalties contributed only small fractions to the optimal solution costs. Furthermore, firm’s resources, e.g. vehicle and labor, were better utilized due to such penalties. Thus, ultimately minimizing total routing costs and total waiting time presents the best utilization of all resources. Therefore, in all perspectives of cost, waiting time, and resource utilization, the VRPSTW outperformed the VRPHTW and the VRPSSTW. Considering the computational point of view, however, the complexity of the problem rapidly increases when time window constraints are extended. The problem then becomes much harder to be solved. The exact-based branch-and-price approach with all proposed SP solution techniques could only solve the VRPSTW up to medium-sized instances in reasonable time. Some other useful algorithms such as metaheuristics should further be explored in combination with the exact-based solution approaches to solve larger instances of the VRPSTW. Besides, non-linear penalty functions, which are more suitable in real-life situation, need to be studied in the future.