Printer Friendly

Evaluating the impact of spatio-temporal factors on construction heuristics for transportation services.

Abstract

In the dial-a-ride services, customers specify pickup and drop-off locations and their times for transport. The operator aims at constructing cheap itineraries while minimizing customer inconvenience. This problem has been studied as the Dial-a-Ride Problem (DARP), which consists of both spatial and temporal factors. This article studies the impact of spatial and temporal variation on multivehicle DARP using route construction heuristics. Our work highlights the impact of these variations on the customer disutility and transportation cost. The study will help the service operators in selecting an appropriate construction heuristic while expanding the DARP service in terms of service area, service duration, or planning for a sudden growth in the number of customers. The results show that if the operator is planning to expand the area of service, the Saving Heuristic is more appropriate for larger operators while Insertion Heuristic with spatial sorting scheme is better for smaller operators with limited number of vehicles. If the operator is expanding the service in terms of service duration, from 8 to 24 hours daily, for instance, or preparing for a growth in the number of customers, the Saving Heuristic is better for both smaller and larger service operators.

Keywords

Dial-a-ride, demand responsive transport, transportation, vehicle routing and scheduling

Introduction

In the dial-a-ride services, or demand responsive transport, customers call an operator for transportation between a pickup and drop-off point within a specific time frame. Such services include ambulatory services, radio cabs, and transportation for disabled or elderly people. In these services, dial-a-ride operators face the problem of scheduling cost-effective itineraries. This scheduling problem is widely studied in literature as a dial-a-ride problem (DARP), which aims at designing efficient vehicle routes for a set of customers where distinct transportation points are provided by each customer. DARP is characterized by a set of m vehicles and n customers. Each customer has a pickup (source) and drop-off (destination) point where the customer has to be transported within a given time frame. Routes are scheduled in such a way so that these result in least transportation cost and customer disutility. Transportation cost is derived from the number of vehicles used and the total distance traveled. Customer disutility is calculated by adding up the total waiting times and deviation of actual times (pickup and drop-off) from desired times. The two objectives--transportation cost and customer disutility--are often conflicting (Cordeau and Laporte 2003b). Therefore, the service operators have to decide on either reducing the transportation costs incurred by the service or reducing the customer disutility of their passengers.

DARP comprises both time-related (temporal) and space-related (spatial) factors. Space-related factors include the area of service, pickup points, and drop-off points. Time-related factors consist of service duration (total hours of the day during which the service is active), pickup times, drop-off times, and service times (time spent in serving a customer). The variations in area of service imply scattering of spatial data, that is, spread of pickup and drop-off points within a given area. On the other hand, variations in service duration imply scattering of temporal data, that is, spread of pickup and drop-off times within a given time span. The spatial and temporal factors become of vital importance when the DARP operator wants to expand the service. Studying the impact of these factors can thus help service providers in estimating the transportation cost and customer disutility. Analysis of such factors for construction heuristics forms the motivation for this study. In this article we have studied the impact of the temporal and spatial factors on static DARP. In static DARP all the information needed to solve the problem is available before initializing the routes. This necessity is different from dynamic DARP, where some of the information is revealed during the construction of routes. We evaluate not only the impact of increase in area but also service duration and increase in number of customers.

For this study we assumed static DARP without ride sharing. Although ride sharing is important in DARP literature, there are applications where it is not allowed. For example, in ambulances, apart from the capacity constraint for these vehicles, ambulatory passengers with special needs for transportation cannot use ride sharing due to allergies or sensitivity to the environmental conditions. The ambulances are mostly owned by NGOs or governments rather than hospitals that travel from a depot to patients/hospitals and then back to a depot. Researchers have discussed in detail the case of route scheduling where ride sharing is not possible (Beaudry et al. 2010; Kergosien et al. 2011). Taxicabs may also avoid ride sharing due to privacy concerns and customer dissatisfaction. Furthermore, Paquette, Cordeau, and Laporte (2009) described many factors that cause degradation to qualitative quality of service (QoS)-related factors caused by ride sharing.

Solving DARP generally requires finding solutions that reduce both transportation cost and customer disutility. Several methodologies have been proposed for this problem that can be divided into two main categories: route construction algorithms (algorithms that construct an initial route) and route optimization algorithms (i.e., that improve the initial routes). In this study we focus on route construction algorithms first, because these serve as a basis for optimization algorithms by providing initial routes (Hosny 2010). Second, better initial routes minimize the computation time of the route optimization algorithms (Xiang, Chu, and Chen 2006). We use three types of route construction algorithms that employ different schemes for evaluating the customer proximity. A construction heuristic can calculate customer proximity (closeness) by using information from the list of customer requests. This information may include time-related (e.g., arrival, departure time), space-related (pickup, drop-off locations, and so on) or both types of information. In literature, we find that most construction algorithms for DARP utilize time-related information (Coslovich, Pesenti, and Ukovich 2006; Diana and Dessouky 2004; Hame 2011; Jaw et al. 1986; Madsen, Ravn, and Rygaard 1995; Toth and Vigo 1996; Wong and Bell 2006). The only two methods that use both the time- and space-related information about customers are proposed in Guo and Liu (2014) and Luo and Schonfeld (2007).

The contribution of this article is the analysis of variations in spatial and temporal factors of DARP and its effects on the three basic types of construction heuristics. The performance is analyzed for the two major aspects of DARP, that is, transportation cost and customer disutility. We found that the transportation cost directly depends on spatial factors while the customer disutility is dependent on the proximity calculation as well as the customers served in a route property of the heuristic. Such an analysis will help the service operators in selecting an appropriate construction heuristic while expanding the DARP service. The three selected construction heuristics are insertions heuristic (IH), savings heuristics (SH), and nearest-neighbor heuristic (NNH). To the best of our knowledge, there has not been any such study. There are various versions of construction heuristics, all of which are inspired from the basic heuristics proposed by Jaw et al. (1986) and Solomon (1987). We use two variations of IH. The first version is called IH-T (IH for Temporal) is meant for evaluating the impact of temporal factors. The other version IH-S (IH for Spatial) is used for evaluating the spatial impact on IH. The reason for choosing these heuristics is that each of these heuristics uses a different way of evaluating the proximity between customers. The IH prioritizes temporal proximity of customers and SH focuses on spatial data, whereas the time-oriented NNH considers both spatial and temporal proximity of customers.

The rest of the article is organized as follows. We begin with an overview of DARP literature with focus on construction heuristics and then formulate the DARP problem into a set of constraints. That is followed by a presentation of the three different types of construction heuristics used in our study. The next section discusses the dataset and experimentation environment, then the results and conclusion are presented.

Related Work

DARP is studied as a variant of vehicle routing problem (VRP) and is an extensively studied problem. For this reason, a complete discussion of DARP literature is out of the scope of this article. Here we provide an overview of the most relevant literature. The commonly used type of construction heuristic for DARP is the insertion heuristic. A basic insertion heuristic is similar to the one proposed by Jaw et al. (1986). One of the well-known insertion heuristics is the parallel insertion heuristic and its variants like the one proposed in other research (Diana and Dessouky 2004; Luo and Schonfeld 2007; Toth and Vigo 1996; Wong and Bell 2006).

A comparative study of construction heuristics is given by Solomon (1987) for VRP with time windows. Unlike Solomon, this research is intended for DARP. Moreover, Solomon uses mixed-integer programming for the analysis of heuristics whereas we use procedural programming. Additionally in this study all the three heuristics are modified to follow an insert-at-end policy in contrast to the best-insert in route construction used by Solomon.

Noda et al. (2003) and Shinoda et al. (2004) conducted a simulation-based study to compare a fixed bus-route system to a dial-a-ride system using successive best insertions. These studies reported the usability of a dial-a-ride model with respect to the limited number of buses and high frequency of demands. Recently a comparative study was done by Kim and Haghani (2011) in which three well-known strategies of DARP were compared: sequential insertion heuristic, parallel insertion heuristic, and cluster-first-route-second heuristic. Their work is different from ours because they focused on multidepot DARP with varying travel times and ride-sharing. Hall, Hogberg, and Lundgren (2012) proposed a model for DARP that accepts vehicle specifications, travel demand, service level, and cost structure as input and reports route schedule as output for DARP. Their system used insertion heuristics to schedule the incoming requests aimed to lower customer disutility and operational cost. A route construction algorithm is presented by Guo and Liu (2014) who consider both the temporal and spatial factors. That algorithm uses an insertion-rejected-reinsertion policy to reduce the operational cost. Hall, Lundgren, and Voss (2015) model a dynamic DARP service operated in Sweden using simulation. Their results show that the chances for better solution increases with imposing less service constraints on the solution. Unlike Hall, Lundgren, and Voss, our study focuses on static DARP. A more detailed overview of literature on DARP can be found in the work of other researchers (Cordeau and Laporte 2003a, 2007; Parragh et al. 2009).

Unlike all of these studies that introduce a variant of construction heuristic (mostly insertion heuristic), our work focuses on the analysis of spatial and temporal factors of DARP. Moreover, unlike most of these related works that study a single heuristic, we evaluate three different types of construction heuristics for DARP.

The DARP Problem

DARP is represented as a directed graph G = (V, A) with a set of nodes (vertices) and arcs. Nodes represent the depot and customer pickup and drop-off points. Arcs represent the distances [d.sub.ij] between the nodes i and j. The set of nodes are represented as V = (0, 1, ..., 2n + 1), where the vertices o and m + 1 represent the depot, vertices (i, ..., n) represent the pickup points and vertices (n +1,..., in) represent the drop-off points. The distances [d.sub.ij] are calculated using the Euclidean distance. The amount of time the customer remains onboard is termed as the ride time.

For all customers, m, let us assume that [ART.sub.m] and [MRT.sub.m] are the actual and maximum ride times. Maximum ride time represents the upper bound on the service time. The customer has to be served before this time limit. Also assume that the customers also specify their earliest and latest pickup times. [EPT.sub.m], [APT.sub.m], and [LPT.sub.m] represent the earliest, actual, and latest pickup times. Vehicles arriving at pickup point before [EPT.sub.m] time have to wait for [customer.sub.m]. Customers are also not willing to avail the service when the vehicles are late beyond their LPT time. Similarly, [EDT.sub.m], [ADT.sub.m], and [LDT.sub.m] show the earliest, actual, and latest dropoff times respectively. [EDT.sub.m] represents the earliest time that the customer can be dropped off at his/her destination. [ADT.sub.m] is the actual time at which the customer was dropped off, and [LDT.sub.m] is the upper bound for drop off time of the customer m.

Following these definitions, the main goal is to design the cheapest possible itineraries (i.e., itineraries with lowest distance traveled by vehicles), subject to the following general DARP constraints for all customers,

[ART.sub.m] [less than or equal to] [MRT.sub.m]

[EPT.sub.m] [less than or equal to] [APT.sub.m] [less than or equal to] [LPT.sub.m]

[EDT.sub.m] [less than or equal to] [ADT.sub.m] [less than or equal to] [LDT.sub.m]

where m is a positive integer representing the number customers' requests. All these three constraints for the static DARP model are described by Diana and Dessouky (2004) and Jaw et al. (1986). Constraint (i) ensures that the customer does not have to sit in the vehicle for longer than a maximum time. Constraints (ii) and (iii) represent time windows that indicate that a customer should not be picked up or dropped off before or after a given time.

Construction Heuristics for DARP

There are various versions of construction heuristics, all of which are inspired from the basic heuristics proposed by Jaw et al. (1986) and Solomon (1987). In this section we briefly describe the three route construction heuristics--IH, SH, and NNH--that we used to determine the impact of spatial and temporal scattering on DARP.

Insertion Heuristic

An insertion heuristic starts with a tour of a small subset of nodes. The starting tour could be a tour on the three farthest nodes forming the largest triangle. It extends this tour by iteratively inserting the nodes that are remaining in the list. In this study we use two versions of IH. In the first version, IH-T, we sort the customers according to the earliest pickup time, whereas in the second version, IH-S, we sort customers according to the distance between depot and pickup point. We used these two different versions of IH to evaluate the impact of spatial and temporal proximities during scheduling. The presented algorithm does not use ride sharing and instead of testing the customers for all possible insertions in a route we simply check for feasible insertion at the end of an existing route (see algorithm 1).

The main steps of the IH without ride sharing are shown in algorithm 1. Steps 2-8 of algorithm 1 check customer c for feasible insertion at the end of route r. If a feasible insertion is not possible, a new route is created in step 9-11, and the customer c is inserted in it.

Savings Heuristic

Savings heuristic aims to save cost by visiting more customers in a single route. The heuristic works by combining multiple routes into a single route to increase the savings. SH for DARP is presented in algorithm 2. The cost equations are described in the following text.
Algorithm 1 Insertion Heuristic

1: SORT customers according to Earliest Pick-up Time for IH-T or
   ascending order of distance between depot and pick-up point for
   IH-S
2: for all customers c in the customer list do
3:    for all existing routes r do
4:       if c can be feasibly inserted in r then
5:          INSERT c in r
6:          BREAK
7:       end if
8:    end for
9:    if feasible insertion is not possible then
10:      CREATE a new route and assign customer to it
11:   end if
12: end for

Algorithm 2 Savings Heuristic

1: CALCUALTE the Savings matrix [S.sub.ij] of all customers
   using equations M,W>(3)>(4)
2: SORT the savings matrix in descending order
3: INITIALIZE a list of routes with each route serving
   one customer
4: for all customers c in the customer-list do
5:    SELECT customer /
6:       if / has not been served then
7:          while routes can be merged do
8:             SELECT a customer j that results in
               highest savings with /
9:             if / can be feasibly merged with j then
10:            MERGE the routes
11:            UPDATE /' to j
12:            MARK i and j served
13:         else
14:            SELECT another j
15:        end if
16:     end while
17:    end if
18: end for


Let the total distance (from depot to customer's pickup point, that is, [d.sub.depot-orgi]; drop-off point, [d.sub.orgi-desi]; and back to the depot, that is, ([d.sub.desi-depot]) traveled for customer [d.sub.i] be represented as [d.sub.i] and the total distance of customer j be [d.sub.j] Then, d is the total distance calculated from merging the routes of these two customers z andj, mathematically:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

>

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

>

The savings equation is given as the following:

[s.sub.ij] = [d.sub.i] + [d.sub.j] - [d.sub.ij] (4)

>

In step 1 of algorithm 2, savings are calculated for all pair of customers. Step 2 sorts the customer pairs in descending orders of savings. Step 3 initializes the routes list containing a route for each customer. Step 5-6 selects a customer i that has not been served with the aim to merge its route with another customer j's route that result in highest savings (steps 7-8). Step 9 checks if the two routes can be combined together without violating the constraints of DARP. Step 10 combine the routes if merging is feasible and updates the route list (step 11). The two customers i and j are then marked as served in step 12.

Time-Oriented Nearest-Neighbor Heuristic

The nearest-neighbor heuristic (NNH) starts each route by finding the unvisited customer nearest to the depot. The algorithm iteratively adds the nearest neighbor of the last customer to the route. This search is continued until the route returns to the depot or all customers are served. The cost function uses three metrics given as follows:

The distance between the drop-off point of customer i and pickup point of customer j is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

The time taken to travel between the drop-off point of i and pickup point of j, [T.sub.ij] is given by

[T.sub.ij] = [D.sub.ij]/Speed (6)

>

where speed is the speed of the vehicle.

The urgency, which is the time remaining to start the service for j after servicing i, [[U.sub.ij], is given by

[U.sub.ij] = [LDT.sub.j] - ([ADT.sub.i] + [T.sub.ij] + [ART.sub.j]) (7)

The cost function [C.sub.ij] is then given in equation 8:

Cij = (w1 * [D.sub.ij]) + (W2 * [T.sub.ij]) + (w3 * [U.sub.ij]) (8)

where, wi + wi + W3 = 1.0. For definitions of [D.sub.ij], [T.sub.ij] and [U.sub.ij] the readers are referred to Solomon (1987).

Note that cost function uses weights w1, w2, and W3 for adjusting the importance of the three metrics, that is, [D.sub.ij], [T.sub.ij], and [U.sub.ij] for calculating the proximity.
Algorithm 3 Nearest-Neighbor Heuristic

1: CALCUALTE the Cost matrix [C.sub.ij] of all customers using
   equations (5), (6), (7), (8)
2: SORT the Cost matrix in ascending order
3: SORT the customer-list in ascending order of distances from
   depot to pick-up point
4: INITIALIZE a list of routes with each route serving one customer
5: for all customers c in the customer-list do
6:    SELECT customer /
7:    if / has not been served then
8:       while routes can be merged do
9:      SELECT a customer j that results in lowest cost when i
10:        if / can be feasibly merged with j then
11:           MERGE the routes
12:           UPDATE /' to j
13:           MARK i and j served
14:        else
15:           SELECT another j
16:        end if
17:     end while
18:   end if
19: end for


NNH for DARP is given in algorithm 3. Step 1 of algorithm 3 calculates the cost between all pair of customers. Step 2 sorts the cost pairs in ascending order. The customer list is also sorted in ascending order of their distance from depot in step 3. Step 4 creates a separate route for each customer. Steps 5-9 select a customer i from the customer list and try to merge it with another customer j that results in the lowest cost. Steps 10-13 combine the two customers i and j in the same route if the merging does not violate any of the constraints and then marked both of these customers as served.

Performance Metrics and Simulations

In the following subsections we discuss the comparison metrics we used and the characteristics of our test instances.

Comparison Metrics

To study the impact of scattering of data for spatial and temporal factors on DARP, we used the following metrics:

* Net distance: The total distance traveled by all vehicles for each test instance.

* Number of vehicles: The maximum number of vehicles used simultaneously. Note that a vehicle can be used to serve multiple routes because it might be dispatched again for another route after completing its current route.

* Customer disutility: The amount of deviation of actual time from the desired pickup and drop-off time in minutes.

* Computation time: The time required to run each test instance.

These metrics are used to compare the performance of selected heuristics on the two major aspects of DARP, that is, transportation cost and customer disutility. In addition to the set of constraints, minimizing transportation cost and customer disutility (or inconvenience) simultaneously makes the DARP different from classical VRP problems (Detti, Papalini, and de Lara et al. 2016; Masmoudi et al. 2016). The transportation cost is calculated from two metrics, that is, net distance traveled and number of vehicles employed. The customer disutility is directly calculated from the customer-disutility metric. Additionally, the number of customers per route is used to demonstrate a vehicle's usage in a route. It can also be used to gain some insight into the reasons why the customer disutility might increase. For instance, if customer served per route is one then there is a little chance of deviation of actual time from desired time, which results in less customer disutility.

Test Instances and Experimentation

All of the experiments were performed using MATLAB 2011a on a machine with Intel Core 13 3.30 GHz processor and with 4GB of RAM. We created our own test instances because the only available benchmarks or test instances are provided by Cordeau and Laporte (2003b). These benchmarks use fixed area of service and are thus not helpful for this study. We generated three sets of test instances named spatial, temporal, and growth data set. The spatial and temporal data sets, as the names indicate, are used for analyzing the impact of scattered spatial and temporal factors on DARP. The third dataset growth is used for evaluating the DARP under increasing customer requests. These test instances are made publically available online at https://github.com/ Darppaper/DARPDATASET. Table 1 provides the description of these three datasets. The spatial dataset has fixed service duration (a temporal factor) while the area of service varies from 5 to 60 square km. Service duration is the total number of hours of the day during which the requests for transportation are processed and customers are served. For the temporal dataset, the area of service (a spatial factor) is fixed while the service duration varies between 2 and 24 hours. As stated above, DARP comprises both spatial- and time-related factors. To introduce only spatial variations in the test instances of spatial dataset, the temporal factors are fixed. Space related features are fixed while the time-related features are varied in the temporal dataset.

The third dataset growth has fixed spatial and temporal factors while the number of requests (or number customers) varies between 50 and 1,000. Additionally, all the datasets have the following common characteristics:

* The location of the depot is selected at the center of area of service.

* Pickup and drop-off points are randomly generated using uniform distribution.

* A time window of 30 minutes is used.

* Service time of 2 minutes is used.

* Vehicle speed is set to 60 km/h.

Although spatial patterns are common among customer requests in logistic-oriented VRP, requests are received from customers (such as factories, stores, shops) whose locations are fixed with repeating flow of goods between certain pickup and drop-off points. DARP literature uses uniform distribution for simulating the customer locations (Bell and Griffis 2010). We therefore use uniform distribution for generating random pickup and drop-off points. Note that our experiments use fixed travel times. Fixed travel time means that the time taken to travel equal distance is same irrespective of the traffic conditions. This implies that the vehicle speed remains constant. In our experiments, we thus have used a constant vehicle speed of 60 km/h. Moreover we assumed a fixed time windows, which is often used in research (Kim and Haghani 2011). We used a time windows of 30 minutes and a service time of 2 minutes. We also experimented with service times of 10 minutes. Since changing the service time from 2 minutes to 10 minutes, we just increased the total transportation cost and did not change the trends of transportation cost. We thus only report the results with service time of 2 minutes.

Results and Discussion

In this section we discuss the results of our experiments of the construction heuristics with the three data sets. These results are also included in table A1-3 in the appendix.

Impact of Area of Service

The results of experimentation on spatial dataset for 1,000 customers are plotted in figure 1, which shows the impact of scattering the spatial data. The numerical values of the results are also given in table Ai in the appendix. Figure 1a shows the result for net distance with the increase in the area of service. It can be seen from figure lA that SH gives the least amount of distance traveled for all instances and NNH gives the highest costs. For smaller areas of service, the difference between the net distances traveled by four heuristics is smaller, but with the increase in the area of service this difference also increases. The reason for this increase is that since customer requests are spread across larger areas, the vehicles have to travel longer, resulting in greater net distances.

For smaller areas of service, the four heuristics almost utilize the same number of vehicles (fig. 1B). However, as the area of service is increased, IH-S and IH-T use fewer vehicles as compared to the other heuristics. On the other hand, SH and NNH show an increasing trend with the increase in area of service. The customer disutility for both SH and NNH slightly decreases with the increase in the area of service as shown in figure ic. IH-S gives the smallest disutility. For IH-S and IH-T, the change in customer disutility is insignificant. The customer disutility for both IH-S and IH-T is less than the other heuristics because these heuristics create more routes as compared to SH and NNH (see fig. iC).

The computation time is shown in figure 1D, which is least for IH-S and IH-T. There is no significant impact of increase in area of service for IH-S and IH-T. However, for SH and NNH, the computation time slightly increases. This increase is due to the fact that with increase in area of service, SH and NNH create more routes.

Impact of Duration of Service

The results of experimentation on temporal dataset for 1,000 customers are shown in figure 2 and in table A2 of the appendix. Figure 2A shows that for increasing duration of service, there is no significant impact on the net distance for all heuristics; it almost remains the same. Among the four heuristics, SH gives least net distance as compared to the other three heuristics. IH-S gives the highest costs in terms of net distance traveled. The reason that net distance is not correlated with service duration is that since the area remains the same, the vehicles have to travel the same distances.

The impact of temporal variation on number of vehicles used is shown in figure 2B. SH and NNH, which most often utilize more vehicles, observe a decreasing trend for increasing service duration. The trend for IH-S is not clear; however, IH-T sees an increase in number of vehicles employed for increasing service duration.

For customer disutility, figure 2C shows that IH-S gives the least values whereas NNH gives the highest values. As the service duration is increased, the customer disutility incurred by SH and NNH increases while for IH-S and IH-T it slightly decreases. This trend can be explained with the help of customers per route metric shown in figure 3.

As described earlier, customer disutility is caused by the deviation of actual pickup and drop-off times from the desired times. When there is a decrease in the number of customers per route, the deviation of times will also decrease and vice versa. Figure 3 shows that for IH-S and IH-T the number of customers per route decreases with the increase in service duration causing the customer disutility to slightly decrease. However, in the case of SH and NNH, customers per route increases for increasing service duration, resulting in an increase in the customer disutility.

The result for computation time is shown in figure 2D. It can be seen from the figure that computation time for all heuristics does not see any enormous change. The two versions of insertion heuristic consume the same amount of time while the SH and NNH take nearly equal time.

Impact of Number of Customers

For any given spatial and temporal data, variation in the number of customers also impacts the performance of the heuristics. From experimentation, it is observed that the cost incurred for all metrics increases with the increase in number of customers. Such trends can be seen in figure 4 and in table A2 of the appendix section. For instance, figure 4A-B shows that the net distance traveled and the number of vehicles used by all heuristics increases with the increase in number of customers. Intuitively, this increase is due to the fact that as the number of requests increases, more vehicles are required to serve all customers, and thus the net distance traveled increases as well. It can be seen in figure 4b that the number of vehicles used by insertion heuristics are significantly more than the other two heuristics.

Figure 4C shows that IH-S incurs least customer disutility and also shows insignificant change for increasing number of customers. The heuristics SH and NNH, which use fewer vehicles, also incur higher customer disutility. Thus it can be concluded that decreasing the number of vehicles increases the customer disutility. For increasing number of customers, figure 4D shows that all the algorithms observe increase in computation time but this increase is more visible for SH and NNH. Moreover, SH and NNH consume the same amount of computation time whereas the two insertion heuristics take equal time.

Since the motivation is to help service operators in selecting an appropriate construction heuristic while expanding the DARP service, all the results are summarized in table 2 to distinguish between heuristics, especially for minimizing the transportation cost and customer disutility. This table lists the heuristics that incur the minimum and maximum value for the comparison metrics. It can be inferred from table 2 that IH-S is preferable from the customer's point of view because it gives low customer disutility. On the other hand, SH is better from the service provider's point of view because it gives lesser net distance traveled. However, since SH also uses more vehicles than IH-S in certain conditions (figs. 1B and 2B), a tradeoff has to be made if few vehicles are available.

Conclusion and Future Work

In this article, we analyzed the impact of spatial and temporal variations on three construction heuristics considering two major aspects DARP: transportation cost and customer disutility. It is found that transportation cost is directly dependent on the spatial factors while the customer disutility is dependent on the customer's proximity calculation of the heuristic as well as its customer-per-route metric. The study will assist DARP service operators in selecting an appropriate construction heuristic while expanding the service in terms of service area, service duration, or preparing for a growth in the number of customers. The results suggest that if the service operator is planning to expand the area of service, the SH heuristic is more appropriate for operators with large vehicle fleet. This is due to the fact that the SH heuristic incurs smaller transportation costs but at the same requires more vehicles for the increasing service area. For smaller service operators with limited fleet, IH-S is economical because it requires a comparatively small number of vehicles compared to other heuristics for an increasing service area. If the operator is expanding the service in terms of service duration, from 8 to 24 hours daily, for instance, or preparing for a growth in the number of customers, the SH heuristic is better for both smaller and larger service operators. The reason is that the SH heuristic incurs smaller transportation costs and also does not see rapid increase in the number of vehicles employed to serve the customers for increasing service duration or for increasing number of customers. Overall, IH-T provides a good compromise between transportation cost, customer disutility, and computation time. Future research directions include the variations of the three construction heuristics for a more constraint dynamic DARP problem that also include ride sharing.

Appendix

Results of the Construction Heuristics with the Three Datasets
Table A1/Results with Spatial Dataset

Heuristic   Service       Net       Number     Customer
             Area       Distance      of       Disutility
             (Km2)                  Vehicles

IH-S           5       6300.6307       44      16214.234
               10      11517-7806      57      17975.360
               20      22353.2232      70      21035.359
               40      45222.9496      75      30278.307
               60      65308.4800      93      35680.391
IH-T           5       6365.0445      103      26822.243
               10      11289.9732      60      29850.819
               20      21979 2648      92      33546.336
               40      43743.4224      67      44131.117
               60      62416.5214      92      51441.847
SH             5       5778.4706       45      170346.172
               10      10220.6664      80      157910.792
               20      20272.4573     145      105258.335
               40      42233-4482     266      59062.870
               60      60855.3308     330      46540.941
NNH            5       6301.7746       48      259378.933
               10      11349.2867      85      260590.181
               20      22490.0277     161      248793.715
               40      46617.3506     294      217068.223
               60      67660.2465     358      209145.894

Heuristic   Service    Computation
             Area          Time
             (Km2)

IH-S           5          0.9964
               10         1.0251
               20         0.9894
               40         1.0247
               60         0.9657
IH-T           5          0.9854
               10         1.0727
               20         0.8995
               40         0.8998
               60         0.9001
SH             5          3.0666
               10         3.2274
               20         3.9956
               40         4.8303
               60         5-0457
NNH            5          2.9323
               10         3.3309
               20         4.0347
               40         4.9177
               60         5.1564

Table A2/Results with Temporal Dataset

Heuristic   Service       Net      Number     Customer
            Duration    Distance     of       Disutility
             (hrs.)                Vehicles

IH-S            2       10285.15      39      20765.056
                4       10568.8053    45      20858.349
                8       10703.8446    40      17877.935
               12       10784.4054   146      14568.276
               16       10765.031    106      14922.450
               24       11060.672    120      12898.595
IH-T            2       10218.7317    72      29754.709
                4       10357.2117    38      30596.755
                8       10526.233     38      30350.011
               12       10284.5611    34      29565.633
               16       10452.607     63      27327.358
               24       10512.5631   108      25079.730
SH              2       9417.1697    174      54909.314
                4       9705.811     115      86715.302
                8       9693.2311     78      157063.683
               12       9262.428      42      178305.606
               16       9341.9934     30      244076.890
               24       9485.0784     18      296724.311
NNH             2       10605.8952   181      79224.348
                4       10582.2869   123      136768.847
                8       10548.1337    81      256347.931
               12       10338.8963    44      341662.197
               16       10462.3851    37      462574.559
               24       10527.3923    18      609168.920

Heuristic   Service     Computation
            Duration        Time
             (hrs.)

IH-S            2          1.0116
                4          0.9958
                8          0.9339
               12          0.9435
               16          0.9817
               24          0.9399
IH-T            2          1.0093
                4          1.0254
                8          0.9315
               12          0.8997
               16          0.9326
               24          0.9395
SH              2          3.846
                4          3.5317
                8          3.299
               12          3.0696
               16          3.0057
               24          3.1059
NNH             2          3.6974
                4          3.428
                8          3.2945
               12          3.0757
               16          3.0821
               24          3.0461

Table A3/Results with Growth Dataset

Heuristic     Number          Net         Number      Customer
            of Customers    Distance    of Vehicles   Disutility

IH-S             50          609.4897         8         419.572
                350         3921.0358        54         4635.228
                500         5543.9925        57         7205.297
                650         7207.2277        86         8661.403
                1000       10981.8047       58        15368.162
IH-T             50          604.0956        15         397.246
                350         3678.8485        24         8594000
                500         5385.9991        49        12388.578
                650         6975.5595        67        17252.179
                1000       10688.9368        99        27942.824

SH               50         544.6686          2        2354.569
                350        3366.2647          7       63205.488
                500        4819.3742         16      106626.150
                650        6277.6768         25      128879 541
                1000       9755.2778         48      194452.901
NNH              50         561.3978          1        8155.090
                350        3713.5393          9      117534.037
                500        5265.6758         10      153581.116
                650        6959.5336         23      200483.057
               1000       10713.6772         47      352782.484

Heuristic     Number       Computation
            of Customers       Time

IH-S             50           0.0485
                350           0.0487
                500           0.0923
                650           0.1972
                1000          1.0251
IH-T             50           0.0466
                350           0.0439
                500           0.0796
                650           0.1723
                1000          0.9332

SH               50           0.0651
                350           0.2202
                500           0.4737
                650           0.9763
                1000          3.2192
NNH              50           0.0844
                350           0.2372
                500           0.4831
                650           0.9297
                1000          3.0016


References

Beaudry, A., G. Laporte, T. Melo, and S. Nickel. 2010. "Dynamic Transportation of Patients in Hospitals." OR Spectrum 32 (1): 77-107.

Bell, J. E., and S. E. Griffis. 2010. "Swarm Intelligence: Application of the Ant Colony Optimization Algorithm to Logistics-oriented Vehicle Routing Problems." Journal of Business Logistics 31 (2): 157-75.

Cordeau, J.-F., and G. Laporte. 2003a. "The Dial-a-Ride Problem (DARP): Variants, Modeling Issues and Algorithms." Quarterly Journal of the Belgian, French and Italian Operations Research Societies 1 (2): 89-101.

--. 2003b. "A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem." Transportation Research Part B: Methodological 37 (6): 579-94.

--. 2007. "The Dial-a-Ride Problem: Models and Algorithms." Annals of Operational Research 153:29-46.

Coslovich, L., R. Pesenti, and W. Ukovich. 2006. "A Two-Phase Insertion Technique of Unexpected Customers for a Dynamic Dial-a-Ride Problem." European Journal of Operational Research 175:1605-15.

Detti, P., F. Papalini, and G. Z. M. de Lara. 2016. "A Multi-Depot Dial-a-Ride Problem with Heterogeneous Vehicles and Compatibility Constraints in Healthcare." Omega. Available at http://dx.doi.Org/io.ioi6/j.omega.2oi6.o8.oo8.

Diana, M., and M. M. Dessouky. 2004. "A New Regret Insertion Heuristic for Solving Large-Scale Dial-a-Ride Problems with Time Windows." Transportation Research PartB: Methodological 38:539-57.

Guo, J., and C. Liu. 2014. "A Spatio-Temporal Based Parallel Insertion Algorithm for Solving Dial-a-Ride Problem." In Control and Decision Conference (2014 CCDC), The 26th Chinese, 3257-61. IEEE.

Hall, C. H., M. Hogberg, and J. T. Lundgren. 2012. "A Modeling System for Simulation of Dial-a-Ride Services." Public Transport 4 (1): 17-37.

Hall, C. H., J. T. Lundgren, and S. VoJS. 2015. "Evaluating the Performance of a Dial-a-Ride Service Using Simulation." Public Transport 7 (2): 139-57.

Hame, L. 2011. "An Adaptive Insertion Algorithm for the Single-Vehicle Dial-a-Ride Problem with Narrow Time Windows." European Journal of Operational Research 209 (1): 11-22.

Hosny, M. I. 2010. "Investigating Heuristic and Meta-Heuristic Algorithms for Solving Pickup and Delivery Problems." Ph.D. thesis, Cardiff University, School of Computer Science and Informatics.

Jaw, J.-J., A. R. Odoni, H. N. Psaraftis, and N. H. M. Wilson. 1986. "A Heuristic Algorithm for the Multi-Vehicle Advance Request Dial-a-Ride Problem with Time Windows." Transportation Research Part B: Methodological 20 (3): 243-57.

Kergosien, Y., C. Lente, D. Piton, and J. C. Billaut. 2011. "A Tabu Search Heuristic for a Dynamic Transportation Problem of Patients Between Care Units." European Journal of Operational Research 214 (2): 442-52.

Kim, T., and A. Haghani. 2011. "Model and Algorithm Considering Time-Varying Travel Times to Solve Static Multidepot Dial-a-Ride Problem." Transportation Research Record:Journal of the Transportation Research Board 2218 (1): 68-77.

Luo, Y., and P. M. Schonfeld. 2007. "A Rejected-Reinsertion Heuristic for the Static Dial-a-Ride Problem." Transportation Research Part B 41 (7): 736-55.

Madsen, O. B. G., H. F. Ravn, and J. M. Rygaard. 1995. "A Heuristic Algorithm for the Dial-a-Ride Problem with Time Windows, Multiple Capacities, and Multiple Objectives." Annals of Operations Research 60:193-208.

Masmoudi, M. A., M. Hosny, K. Braekers, and A. Dammak. 2016. "Three Effective Metaheuristics to Solve the Multi-Depot, Multi-Trip Heterogeneous Dial-a-Ride Problem." Transportation Research Part E: Logistics and Transportation Review 96:60-80.

Noda, I., M. Ohta, K. Shinoda, Y. Kumada, and H. Nakashima. 2003. "Evaluation of Usability of Dial-a-Ride Systems by Social Simulation." In Multi-Agent-Based Simulation III, ed. D. Hales, B. Edmonds, E. Norling, and J. Rouchier, 167-81. Lecture Notes in Computer Science 2927. Berlin: Springer.

Paquette, J., J.-F. Cordeau, and G. Laporte. 2009. "Quality of Service in Dial-a-Ride Operations." Computers and Industrial Engineering 56:1721-34.

Parragh, S. N., K. F. Doerner, R. F. Hartl, and X. Gandibleux. 2009. "A Heuristic Two-Phase Solution Approach for the Multi-Objective Dial-a-Ride Problem." Networks 54 (4): 227-42.

Shinoda, K., I. Noda, M. Ohta, Y. Kumada, and H. Nakashima. 2004. "Is Dial-a-Ride Bus Reasonable in Large Scale Towns? Evaluation of Usability of Dial-a-Ride Systems by Simulation." In Multi-Agent for Mass User Support, 105-19. Lecture Notes in Computer Science 3012. Berlin: Springer.

Solomon, M. M. 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints." Operations Research 35 (2): 254-65.

Toth, P., and D. Vigo. 1996. "Fast Local Search Algorithms for the Handicapped Persons Transportation Problem." In Metaheuristics: Theory and Applications, ed. I. H. OsmanandJ. P. Kelly, 667-90. Berlin: Springer.

Wong, K. I., and M. G. H. Bell. 2006. "Solution of the Dial-a-Ride Problem with Multidimensional Capacity Constraints." International Transactions in Operational Research 13:195-208.

Xiang, Z., C. Chu, and H. Chen. 2006. "A Fast Heuristic for Solving a Large-Scale Static Dial-a-Ride Problem Under Complex Constraints." European Journal of Operational Research 174 (2): 1117-39.

Adnan Noor Mian

Information Technology University Lahore, Pakistan

Amina Fahim

Information Technology University Lahore, Pakistan

Abdul Hameed

Corresponding Author

Information Technology University Lahore, Pakistan

abdul.hameed@itu.edu.pk

Caption: Figure 1A Impact of Spatial Variation on DARP Service: Net Distance

Caption: Figure 1B Impact of Spatial Variation on DARP Service? Number of Vehicles

Caption: Figure 1C Impact of Spatial Variation on DARP Service: Customer Disutility

Caption: Figure 1D Impact of Spatial Variation on DARP Service: Computation Time

Caption: Figure 2A Impact of Temporal Variation on DARP Service: Net Distance

Caption: Figure 2B Impact of Temporal Variation on DARP Service: Number of Vehicles

Caption: Figure 2C Impact of Temporal Variation on DARP Service: Customer Disutility

Caption: Figure 2D Impact of Temporal Variation on DARP Service: Computation Time

Caption: Figure 3 Customers per Route

Caption: Figure 4A Impact of Variation in Number of Customers: Net Distance

Caption: Figure 4B Impact of Variation in Number of Customers: Number of Vehicles

Caption: Figure 4C Impact of Variation in Number of Customers: Customer Disutility

Caption: Figure 4D Impact of Variation in Number of Customers: Computation Time
Table 1/Data Sets Information

Data Set   Number of    Service      Service
           Requests     Duration     Area

Spatial    1,000        8 hours      5-60 [Km.sup.2]
Temporal   1,000        2-24 hours   10 [Km.sup.2]
Growth     50-1,000     12 hours     10 [Km.sup.2]

Table 2/Summary of Minimum and Maximum Costs Incurred

                                    Value

                             Minimum   Maximum

Net Distance                   SH        NNH
Customer Disutility (min.)    IH-S       NNH
Number of Vehicles            IH-T       NHH
Comp. Time (sec.)             IH-T       SH
COPYRIGHT 2017 American Society of Transportation and Logistics, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mian, Adnan Noor; Fahim, Amina; Hameed, Abdul
Publication:Transportation Journal
Article Type:Report
Geographic Code:7IRAN
Date:Mar 22, 2017
Words:7315
Previous Article:Discrete time hazard modeling of large motor carriers' longitudinal safety performance.
Next Article:Factor market myopia: a driver of factor market rivalry.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters