یک سیستم پشتیبانی تصمیم گیری مسیریابی خودرو و سوخت گیری برای وسایط حمل موتوری با تقاضاهای حساس به زمان

Given the recent trend of raising fuel cost and the increased time-sensitiveness of shippers, an extensive pressure is placed on the motor-carrier industry to meet the time-constrained customer demands at minimum fuel cost. We propose a decision support system that allows motor carriers to route each vehicle such that the vehicle not only visits all the customers in time (without violating time windows), but also utilizes the “cheapest” gas stations (cheapest truck stops in the region) as refueling points during the tour. While this approach does not necessarily minimize a vehicle's fuel consumption, as it often suggests using non-shortest routes with cheap gas stations (truck stops), it allows the vehicle to reduce the unit cost of buying fuel. Computational testing shows that the proposed approach may attain up to 4.29% savings in fuel cost for motor carriers.

U.S. motor carriers, including the asset-based third-party logistics companies (3PLs) and the shippers with private fleets, are currently facing a challenging business environment for two reasons. The first is the raising fuel cost. It is well known that, during the last few years, fuel prices have increased dramatically by more than 100%, and that thousands of U.S. motor carriers went bankrupt because of such price hikes (Transport Topics [13]). The second is the increased time-sensitiveness of customers. Because of the growing use of lean and just-in-time operations in the manufacturing sector (a major customer segment for motor carriers), many shippers are now imposing time-window constraints on their demands (Ohlmann and Thomas [9]). Hence, an extensive pressure is placed on motor carriers to dispatch their pickup and delivery vehicles in such a way that they can meet the time-sensitive customer demands at minimum fuel costs. Many carriers are using the following two strategies to cope with these challenges. The first is to reduce the fuel consumption of each vehicle by scheduling the customer visits such that the total travel distance during a tour can be minimized without violating time windows. This can be accomplished by using the techniques (and the software products) that solve the time-constrained vehicle routing problems (Bell and Griffis [1]). The second is to reduce the unit-cost of buying fuel (cost per gallon). This is usually accomplished by using the “purchase contract” strategy, in which a carrier makes a commitment to buy certain amounts of fuel from a specific truck stop (typically located near the company depot) to obtain price discounts. Many carriers believe that the joint use of these two strategies would minimize their fuel costs in the long run. In theory, however, the use of these two strategies may not necessarily minimize the fuel cost of carriers. The reason is that, while the price discounts the motor carriers obtain by using purchase contracts typically range from ¢3 to ¢5 per gallon, the difference (variance) of fuel price among truck stops in the same region often goes beyond ¢10 per gallon (see, e.g., Transport Topics [14], or any publicly available fuel-price data). This pattern implies that carriers may attain larger discounts in fuel price by refueling their vehicles at “cheap” truck stops along the route (during the tour) than by using the conventional purchase-contract strategy, which limits the choice of truck stops. From the fleet managers' standpoint, therefore, it may be more logical to use an alternative refueling strategy in which each vehicle is routed such that: (i) the vehicle not only visits all customers in time (without violating time windows) but also finds cheap truck stops along the route, so that (ii) the vehicle can be asked to refuel at these “cheap” truck stops. This paper describes the work being carried out to develop a decision support system for motor carriers that is designed to address the following two questions jointly: (i) “Which route should a truck use to minimize fuel consumption”, and (ii) “Where (at which fuel station) should a truck buy fuel to minimize the fuel-procurement cost”. We develop a technique that seeks to minimize the fuel cost of operating a vehicle by jointly making the routing and refueling decisions, while enforcing the time-window constraints. This method allows carriers to consider the trade-off between using the shortest route (which can minimize the fuel consumption) and using non-shortest routes with cheap truck stops (which can minimize the unit cost of buying fuel). To the best of our knowledge, no study has considered this type of problem in the past. The contribution of this paper is threefold. First, we present a problem (model) that jointly addresses the time-constrained single-vehicle routing problem, known as the traveling salesman problem with time windows (TSPTW), and the vehicle-refueling problem. This model, which is denoted hereafter as the traveling-salesman problem with time windows and refueling (TSPTWR), was developed by working closely with motor carriers to maximize its workability in the field. Second, we propose a metaheuristic method for the TSPTWR. Our method seeks both the route and the sequence of truck stops, which (in combination) minimize the fuel cost of operating a vehicle. Third, we apply our method to both the actual and hypothetical instances, and test its effectiveness. We show that our method provides considerably lower fuel costs than the conventional method, which combines the “shortest-route” and “purchase contract” strategies.

This study provides two types of implications to practitioners. First, motor carriers, asset-based 3PLs, and shippers with private fleet may wish to re-consider their routing/refueling strategies. Our computational results suggest that the fuel cost (refueling cost) of vehicles can become noticeably lower by using the proposed “refuel over the road” strategy, in lieu of using the conventional approach. Thus, rather than negotiating price discounts with a limited number of truck stops near their depots, motor carriers may want to start looking at much wider geographic regions in search for the truck stops that offer significantly lower fuel prices. Second, consulting firms, fuel-optimizer vendors, and other software companies may wish to develop vehicle-routing software products that can solve the TSPTWR (perhaps by using the technique proposed in this paper). Our computational testing shows promising results for using this type of software products in the field. Given that the trucking industry can possibly save billions of dollars in fuel cost by using the approach proposed in this paper, it is possible (even likely) that motor carriers show strong interests in using such software products once they are developed. One limitation of this study is that our TSPTWR model may underestimate the costs associated with travel miles. Appendix A shows that, in our model, the only cost associated with travel miles is the fuel cost. In reality, however, there are other costs that can increase with trip miles. These include, but are not limited to, vehicle maintenance costs and driver wages (truck drivers are typically paid by miles or hours). This implies that, if these other “distance-related” costs are considered, the cost-saving potential of our method (which often suggests using non-shortest routes) may become lower than that reported in this paper. Although we believe that our approach (fuel-cost minimization) properly reflects the goal of many carriers, future research may wish to develop an alternative TSPTWR form that also considers other (i.e., non-fuel) costs.