Most of our daily requirements are made by the service provider coming to our premises. These services are home delivery of Pizza within 30 minutes, transportation service of office picking all employees or school children, Milkman delivering milk door-to-door and postal/courier services. In such services, service delivery and timely service are very important. These issues mainly require scheduling and routing of service vehicles.
The objective of most routing and scheduling problems is to minimize the total cost of providing the service. The scheduling of customer service and the routing of service vehicles are at the heart of many service operations.
Vehicle Routing and Scheduling
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. Objective of such problems is to minimize the time and distance traveled. Many methods have been developed for searching for good solutions to the problem, but for all but the smallest problems, finding global minimum for the cost function is computationally complex. Hence many good heuristics have been developed for these types of problems which yield good solutions if not optimal solutions.
Vehicle routing and scheduling problems are relatively complicated as, there are many different types of problem that can arise, each of which needs to be understood and approached in a different way, , there are many detailed aspects that need to be taken into account and there are a number of different methods or algorithms that can be used to produce solutions.
Problem Types – The different types of problems are
- Strategic problems are concerned with the longer-term aspects of vehicle routing and scheduling, in particular where there is a regular delivery of similar products and quantities to fixed or regular customers.
- Tactical problems are concerned with routes that have to be scheduled on a weekly or a daily basis.
- Interactive basis allows the scheduler to use the computer to derive the most effective routes. Actual demand data are used rather than historical demand, and these ‘real-time’ data provide the basis on which routes are scheduled.
Characteristics of Routing and Scheduling
Routing and scheduling problems are often presented as graphical networks. Circles are called nodes and represent pickup and/or delivery points. A specific node represents a depot or home node, from which the vehicle’s trip originates and ends. Connecting these nodes are line segments referred to as arcs. Arcs describe the time, cost, or distance required to travel from one node to another. Undirected arcs are represented by simple line segments. Directed arcs are indicated by arrows.
Feasibility – Minimum-cost solution or any other criterion like time or distance traveled is subject to the tour being feasible. Feasibility implies that
- A tour must include all nodes
- A node must be visited only once
- A tour must begin and end at a depot.
Route: Sequence in which the nodes (or) arcs are to be visited
Schedule: Specifies when each node has to be visited
Routing and Scheduling Problems
Various routing and scheduling problems are
- Traveling Salesman problem (TSP) – We begin with a set of nodes, to be visited by a single vehicle. The nodes may be visited in any order, there are no precedence relationships, the travel costs between two nodes are the same regardless of the direction traveled, and there are no delivery-time restrictions. In addition, vehicle capacity is not considered. The output for the single-vehicle problem is a route or a tour where each node is visited only once and the route begins and ends at the depot node. The tour is formed with the goal of minimizing the total tour cost.
- Multiple traveling salesman problem (MTSP) – It is an extension of the traveling salesman problem and occurs when a fleet of vehicles must be routed from a single depot. The goal is to
- generate a set of routes, one for each vehicle in the fleet but, a node may be assigned to only one vehicle with vehicle will have more than one node assigned to it. There are no restrictions on the size of the load or number of passengers a vehicle may carry. The solution to this problem will give the order in which each vehicle is to visit its assigned nodes. The objective is to develop the set of minimum-cost routes, with cost may be monetary amount, distance, or travel time
- Vehicle routing problem (VRP) – If we now restrict the capacity of the multiple vehicles and couple with it the possibility of having varying demands at each node, the problem is classified as a VRP.
- Chinese postman problem (CRP) – if the demand for the service occurs on the arcs, rather than at the nodes, or if demand is so high that individual demand nodes become too numerous to specify, we have a CRP
| Problem | Demand | Arcs | Depot count | Vehicle Count | Vehicle Capacity |
| Traveling salesman problem | At the nodes | Directed or undirected | 1 | =1 | Unlimited |
| Multiple traveling salesman problem | At the nodes | Directed or undirected | 1 | >1 | Unlimited |
| Vehicle routing problem | At the nodes | Directed or undirected | 1 | >1 | Limited |
| Chinese postman problem | On the arcs | Directed or undirected | 1 | ≥1 | Limited or unlimited |
Solution Approach to Routing and Scheduling Problems
Two commonly used heuristics for the traveling salesman problem are the nearest neighbor procedure and the Clark and Wright savings heuristic.
Nearest Neighbor Procedure (NNP) builds a tour based on the cost or distance of traveling from the last-visited node to the closest node in the network. The steps in NNP are:
1) Start with a node at the beginning of the tour (say depot node)
2) Find the node closest to the last node and add to the tour. If the closest node is
already in the tour or already there in the path then select next closest node.
3) Go to step 2 until all nodes have been added
4) Connect the first and the last node to form a complete tour
Clark and Wright Savings Heuristic (C-W) – Clark and Wright (C-W) algorithm was developed by Enter G Clarke and J. W. Wright. The basis for C-W algorithm is savings concept where these savings are realized by linking pairs of delivery points served by a single depot in the network. First step in C & W heuristic is to select a node as depot node and label as node 1.
To understand the savings concept, assume n-1 vehicles are available where n is the number of nodes. Each vehicle travels from the depot directly to the node and return to the depot. As we can see in the network below for milk delivery example, one vehicle goes from depot to node 2 and come back and other vehicle goes from depot to node 3 and comes back to depot (node 1).
Scheduling Service Vehicles
Scheduling problems have delivery-time restrictions with specified starting and ending times for a service in advance. Subway schedules fall into this category. A service scheduling problem is called two-sided window if the time limits are specified such as a delivery has to be made between 11 am and 2 pm. A service scheduling problem is called one-sided window if a service specifies that it should precede a given time, for example the case of newspaper, delivery should complete before 7 am.
These problems consists of a
- set of tasks, each with starting time and ending times
- set of directed arcs with starting and ending locations.
The set of vehicles may be housed at one or more depots.
Deadhead Time
Deadhead time is a user-specified period of time such that start time of task j must be longer than the end time of task i. It is the non-productive time required for the vehicle to travel from one task location to another or return to the depot empty.
The concurrent Scheduler Approach – This heuristic is used to solve the above type of scheduling problem. The procedure is as
- Order all tasks by starting times
- Assign first task to vehicle 1
- For the remaining number of tasks, assign the next task to vehicle that has the minimum deadhead time to that task. Otherwise create a new vehicle and assign the task to it.