Free Papers | Free Sample Business Term Paper - Commercial Vehicle Scheduling
THE USE OF VARIABLE TRAVEL TIME INFORMATION TO VEHICLE SCHEDULING - A UK EXAMPLE
ABSTRACT
Most current commercial vehicle routing and scheduling techniques are based upon minimising mileage; operators complain that the accuracy of the associated time calculations is poor, particularly when vehicles travel through congestion zones. These mathematical models are often incapable of supporting all of the constraints inbuilt in a transport problem. When, scheduling tankers transporting hazardous materials, the legal constraints placed both on the driver and the loading of the tankers are often simplified to ease the modelling. Models have only recently been proposed which can include the considerable amount of complexity that comes with using time dependent travel time data. This research is intended as an application of scheduling using variable travel time information and designed examine the possible advantages that using variable travel time could bring to the logistics industry and particularly the movement of hazardous products in road tankers.
"Research into vehicle routing problems (VRP) has been carried out since 1959[1]. Since then VRP has been the focus of large amounts of research, the survey by Bodin et al.[2] present an early and comprehensive survey on the various forms the VRP can take. Toth and Vigo [3] provide an updated survey on VRP problems and solution techniques. The majority of research into VRP has focussed on building effective or optimal routes using static or fixed travel times between locations. Multiple objectives can be applied to the VRP problem including, minimising cost (fixed and variable), ensuring the workloads are evenly spread between vehicles or maximising the usage of the vehicles. Many constraints have also been included within the VRP some of the more commonly applied constraints include, time windows on service, capacity of vehicles and legal driving allowance.
Despite the multiple possible objectives and constraints, research has only just started to focus on improving the robustness of the schedule produced. This new research ensures that schedules produced are more reliable by including all available information about the congestion effects on the roads into the scheduling process. Research into VRP has included trying to avoid congestion by redirecting routes around known congestion or just accounting for the known congestion effect in current planning [4-7]. Research into congestion effects suggests up to 80% of delays on the road are caused by known, repeating congestion. Advanced knowledge of where congestion is most prevalent have allowed techniques including the Road TimetableÔ [8] to be developed so that routing and scheduling packages can make allowances for congestion.
The focus of this research project is to take the Road TimetableÔ [8] and apply it to a real life situation, to determine what the effective benefits from scheduling using variable travel time data. This research based on vehicle used by a UK Chemicals and Petroleum distribution firm. Chemicals and Petroleum distribution or Tanker scheduling has additional specialist constraints that are not normally applied to VRP problems and additional implications.
TANKER SCHEDULING
Within Tanker scheduling there are three very different problems; multi-drop, single-drop and tramping. The multi-drop problem consists of having more than one drop on the vehicle as it leaves the starting depot, this problem is the focus of the research project.
The multi-drop problem has a series of constraints; some of these are specific only to tanker scheduling. Loading and unloading sequences for a tanker is more important than for conventional vehicles. A tanker trailer is split into separate pods unloading these in an incorrect order would lead to balance issues for the vehicle during the remaining trip, making the vehicle unstable and potentially dangerous. This sequence needs to be determined before the tanker leaves the depot and must be adhered to as swapping the contents of the pods while away from the depot is impossible. Swapping the Pod contents requires the pumping in and out of the contents and the cleaning of the destination pod before pumping begins.
Some of the more common constraints considered in practical VRP relate to multi-commodities. In the food retail industry this constraint insists on separating chilled, frozen and ambient food stuffs. In the tanker industry each pod can carry a separate commodity type, normally related i.e. petroleum or food stuffs. Some companies carrying particularly petroleum insist that the final pod carries a less combustible chemical for safety reasons.
Many VRP have time window constraints imposed to ensure that service begins within a certain time horizon; this applies equally to tanker scheduling. Another standard constraint within most VRP is a capacity constraint of some kind. Within tanker scheduling this constraint can be a very simple, as the capacity of a tanker is based only on the number of pods. Each delivery made by the tanker has to be for an integer number of pods.
Another common VRP constraint that is included within tanker scheduling is the use of an heterogeneous fleet. This is important in two main ways; it is often cheaper to dispatch a smaller vehicle as opposed to a large vehicle and some locations requiring a delivery will only be able to receive a delivery from a certain type of vehicle.
Depending on the goods being transported extra legal constraints may need to be included. These should be included on a case by case basis as it may not always be necessary to include more constraints and restriction on top of the heavy goods vehicle (HGV) driving restrictions.
Benefits that scheduling alone offer to haulage operators can be extended, by included variable travel time information, to include more efficient use of fleet, reduced fuel costs, a more robust schedule less likely to be disrupted by congestion and a more accurate estimation of the true costs involved in implementing the schedule. From an holistic stand point avoiding congestion should reduce fuel consumption and the carbon footprint made by the haulage industry. “The pollution attributed to a heavy goods vehicle stood in congestion is five times that of a heavy goods vehicle not caught in congestion”. Looking at tanker scheduling specifically, keeping vehicles transporting dangerous chemicals away from congested areas of the road network should hypothetically reduce the risk of transporting these chemicals.
PROBLEM FORMULATION
The problem explored consists of only a single depot but could be extended to a multi-depot option. The set of customers is denoted by N andthe set of vehicles by K. Each customer, i Î N, has a delivery pod requirement p(i) with an expected delivery time of s(i), a time window [e(i),l(i)] for arrival and a vehicle type type(i), indicating only vehicles of this type or smaller can make this delivery.
The set of vehicles K represents a heterogeneous fleet of vehicles. Each vehicle k Î K, has a capacity allowance Ck, a starting time τk, a maximum driving time Dk, a working time Uk , a vehicle type Vk and a loading time loadk is also required for the depot. Although the break times throughout the day are based on the driver's requirements, in this definition the driver and vehicle are coupled together so there is also drivekand breakk which represent the amount of time driving (drivek) of vehicle k before a break of length (breakk) must be taken.
The traveling times between locations are all known and dependent on the starting location and the ending locations as well as the time of departure. c( i, j, f), this is calculated from the recorded tracking data from ITIS holdings Plc, is defined as the traveling time from i to j, starting at time f for any pair of locations{ i , j } Ì N È{0}.
The vehicles make up a heterogeneous fleet, therefore each vehicle must be treated as unique so a single vehicle route for vehicle k is defined as Rk = [] as the ordered trips to be made by vehicle k, where nk represents the number of trips on vehicle k. is defined as the path of customers required to be delivered to by vehicle k in trip i, represents the number of stops on the complete path, including depot stops, for vehicle k in trip i; by convention, and are identified with 0, that is, the trip starts and ends at the depot.
The arrival time at a service location for a customer i Î N is denoted by a(i), each service also has a variable b(i) representing the break taken before the delivery commences. The arrival time is defined as the leaving time from the previous location plus the travelling time; by convention a() = τk, a() = a() and s() = 0 s() = loadk.
[1.1]
The break time previous to each delivery is defined either as; zero, the waiting time due to arrival prior to time window opening or a required driving break.
[1.2]
The required break due to travelling req_break() is further defined using equations 1.3 ,1.4 and 1.5.
[1.3]
The break taken up to this point the vehicle route, break_taken(), is calculated using equation 1.4 and the travel time used up to the point in the vehicle route, travel_time(), is calculated using equation 1.5.
[1.4]
[1.5]
The only constraint applied directly to each individual customer is that the delivery is started within the given time window. This is a time window for the start of delivery and not on completion.
, [1.6]
The amount of time a vehicle is allowed to operate is restricted both in terms of driving and working time. Therefore constraints are required to ensure that vehicles obey these maximum working time constraints, 1.7 and 1.8 enforce the restrictions on driving time and working time respectively.
( ) [1.7]
(" ) [1.8]
Constraint 1.8 includes the break time within the working time allowance. This is important to ensure that time spent waiting is not used elsewhere, for example waiting for three hours for a time window to open should not allow the driver to continue his shift by an extra three hours. This does not follow the current UK interpretation of the Working Time Directive, which allows the use of “periods of availability” POA to be excluded from the working time calculations.
The departing capacity of the trip needs to be calculated and checked against the capacity of the vehicle. As shown in constraint 1.9.
, (" , i=1,,nk) [1.9]
The final constraint enforces the requirement that the vehicle selected to make the service is able to do so. The vehicle type for every service scheduled in every trip must have a type(i) greater than or equal to the vehicle type Vk.
(" , j=1,...,, i=1,,nk)[1.10]
As with many VRP problems, the objective function simply involves minimising the cost involved in delivering to a number of customer locations, the cost in this formulation is based on travelling time as opposed to travelling distance.
Min [1.12]
SCHEDULING ALGORITHM
This algorithm is a two phase algorithm. The first phase is a constructive phase, creating a feasible solution using a parallel insertion algorithm based on the method described in Potvin and Rousseau [9]. The second phase is a tabu search algorithm similar to the approach by Gendreau et al. [10].
TESTING METHODOLOGY AND INDICATIVE RESULTS
Research by Beggs [12] indicates that, particularly within tanker haulage, congestion is having an increasing effect on the trips operated. Beggs [12] defines any route whose trip time is over an hour longer than planned as having been effected by congestion. Of the results shown, the number of trips effected by congestion depends a lot on the path the trip takes but congestions typically effects between 8%- 26% of the trips studied. This research looks only at the completion times of planned trips.
Research by Maden [11] looks at the effects congestion has on service levels throughout the day. Using recorded congestion data a new algorithm was designed to schedule using this information. The algorithm was then tested on a series of controlled datasets against schedules produced using static traveling time information, which do not have any congestion effects included within it. Two series of static traveling times were used Quick and Slow. Quick is representative of the traveling times recorded when the roads are free of congestion. Slow is representative of extending travel time to allow for congestion.
When the routes, generated using either of the two static time and distance matrices, have real recorded travel times, with congestion effects, retrospectively applied 50%-80% of the routes generated had errors associated with them. These errors included time deliveries being missed, overtime payments required or orders being bumped to the next day in order to avoid legal constraints being broken. This study looked at the effect at every point through out the day and set no acceptable limit on congestion effects.
This survey also suggested that in direct comparison between the solutions generated using the three different data sources, before congestion was taken into account, the solutions using the congestion data were 6.1% more costly in traveling time than using the quick data and 4.8% better than those using the slow data. Once congestion factors were added to the solutions, the solutions generated using the congestion data proved to be 2.2% and 3.1% better than the quick and slow solutions.
Benefits that scheduling alone offer to haulage operators can be extended, by included variable travel time information, this should lead to more efficient use of fleet, reduced fuel costs, a more robust schedule less likely to be disrupted by congestion and a more accurate estimation of the true costs involved in implementing the schedule. From an holistic stand point avoiding congestion should reduce fuel consumption and the carbon footprint made by the haulage industry. “The pollution attributed to a heavy goods vehicle stood in congestion is five times that of a heavy goods vehicle not caught in congestion”. Looking at tanker scheduling specifically, keeping vehicles transporting dangerous chemicals away from congested areas of the road network should hypothetically reduce the risk of transporting these chemicals.
To provide an objective view as to what advantages, if any, could be achieved, if congestion information is used within the scheduling process, the testing structure shown in figure 1.1 has been designed.
Figure 1.1: Testing Methodology Structure
Within figure 1.1 Block A represents the congestion data constructed into a useable form as described by Eglese et al. [8], Block B represent a time and distance matrix using fixed travel times throughout the day. These fixed times are based on the calculated average travel times throughout the day. Block C is the algorithm designed to solve the tanker scheduling problem. The scheduling algorithm will provide two different solutions for comparison (D and E) and the chemical and Petroleum Company currently employs a manual method of scheduling (F). Comparisons between solutions D,E and F will give the theoretical benefits of using the two scheduling methods over a the hand designed method. The comparison should also provide the theoretical benefits of scheduling including recorded congestion effects. The comparisons between D and E were included within Maden [10] and the type of comparison between E and F is used in most case study approaches to VRP.
We are extending the current techniques to be able to measure any potential benefits by including the 80% predictable congestion or whether these benefits highlight by the comparison between D and E are reduced/increased when exposed to include real life examples of 100% congestion.
The designed routes of D,E and F are retrospectively analysed with the actual recorded traffic conditions from the day of the schedule producing the routes and timings shown in H, I and J comparison between this solutions should accurately answer the questions about potential benefits highlighted by this research.
CONCLUSIONS
Although the results are only indicative they show that there is a potential of between 2.2% and 3.1% economic and fuel savings, leading onto environmental savings. The robustness of the schedule produced is increased as currently 50%-80% of schedules are negatively affected by congestion often in very minor ways but these minor effects cause 8%-26% of all trips in the case study [12] to be significantly effected by over an hour.
REFERENCES
1.Dantzig, G.B., Ramser H.J., (1959) The truck dispatching problem. Management Science 6(1): 80-91
2.Toth P, Vigo D (eds) (2002) The Vehicle Routing Problem. Society for Industrial & Applied Mathematics, SIAM, Philadelphia
3.Bodin L, Golden B, Assad A, Ball M (1983) Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research 10: 63-211
4. Fleischmann, B., Gietz, M., Gnutzmann, S., (2004) Time-varying Travel times in vehicle routing, Transportation Science 38: 160-73
5.Ichoua, S., Gendreau, M., Potvin, J-Y., (2003) Vehicle dispatching with time-dependant travel times, European Journal of Operational Research 144: 379-96
6.Kim, S., Lewis, ME., White, CC III.,(2004) Optimal vehicle routing with real-time traffic information, Working Paper, College of Engineering, University of Michigan
7.Kim, S., Lewis, ME., White, CC III.,(2004) State space reduction for non-stationary stochastic shortest path problems with real-time traffic information, Working Paper, College of Engineering, University of Michigan
8.Eglese, R., Maden, W., Slater A., (2006) A Road Timetable™ to Aid Vehicle Routing and Scheduling,Computers and Operations Research 33: 3508-3519
9.Potvin J-Y., Rousseau, J-M., (1993) A Parallel route building algorithm for the vehicle routing and scheduling problem with time windows,European Journal of Operational Research 66: 331-340
10.Gendreau, M., Hertz, A., Laporte, G.,(1994) A tabu search heuristic for the vehicle routing problem, Management Science 40: 1276-1290
11.Maden, W., (2006) Models and Heuristic algorithms for complex routing and scheduling problems, Ph.D. Thesis, Department of Management Science, Lancaster University Management School Lancaster, UK.
12.Beggs, E., (2007) How is increasing congestion effecting road freight distribution? - A case study of BOC Gases Ltd. Department of Transport and Hospitality management, The University of Huddersfield.
We provide a professional essay writing service that thousands of our customers use as an effective way of improving their grades, improving their research and saving them lots of time.
