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

AbstractIn 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

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: |