A Dial-a-Ride Problem Applied to Saharan Countries: The Case of Taxi Woro-Woro

Moustapha Diaby¹, Brou Laurent Anicet Koua², Etienne Soro¹

¹LASTIC-ESATIC Abidjan, Cote d’Ivoire.
²MNTI-INPHB Yamoussoukro, Cote d’Ivoire.

DOI: 10.4236/ojop.2020.94010                

Abstract

In a context of increasing competition and sustainable development, service prices and unused capacity enhancement play a crucial role in freight or people transportation management. The focus of the paper is on a Dial-a-ride Problem in the Saharan country context, for the particular of Taxi “woro-woro”1. More precisely, these taxis help to transport groups of people without any affinity, from point A to point B without stopping. Also, we propose for this problem an exact solution based on a mix integer program (MIP). A secondary study on a random instance generation algorithm is presented, which allows us to have a diversified and varied benchmark on which to apply our MIP program.

Keywords

Mix Integer Programming, Dial-a-Ride Problem, Instance Generation, Saharan Countries, Taxi “Woro-Woro”

1. Introduction

The establishment of a coordinated and cost-effective transport system for “woro-woro” taxis is of particular importance in a booming economic sector.

Transport services of the “woro-woro” type allow the intra and inter-city circulation (pickup and drop-off) of people from various fields of activity. This includes students, employees in the public and private sectors, traders, businessmen, informal workers, housewives, but also the unemployed and the unemployed.

According to Jérôme ALOKO-N’GUESSAN [1], another main function of the “woro-woro” is economic. Indeed, they provide relatively significant income to operators of this type of transport as well as to town halls. In addition, they reduce travel costs for users following an acceptable value for money.

The more “woro-woro” taxi drivers are able to perform many transport tasks and also reduce travel costs, the more income will be generated. In truth, better planning of these transport tasks, which is akin to a Dial a Ride Problem (DARP) [2], can be achieved using the optimization method. And this one can improve this sector in terms of customer satisfaction and revenue. Because as said Toth et al. [3], computerized procedures based on optimization techniques allow savings between 5% and 20% of transport costs.

The rest of this article is organized as follows. First of all, we formally describe the DARP in general than in the particular case of the Saharan countries, notably Côte d’Ivoire and the reasons for studying this problem. The following section is devoted to the mathematical description of the DARP problem applied to “woro-woro” context. Section 5 focuses on the generation of instances that will help to verify our model. While Section 6 presents the method of solving and computational experiments.

2. Dial a Ride Problem

In recent years, the public transport offer in Cote d’Ivoire has steadily deteriorated, contrary to the demands and the demands of the uses that remain growing, making these means of transport less competitive [4]. The use of the individual car remains fairly widespread in urban areas because of its availability and efficiency despite the few disadvantages that it has in this case. Cost of use (fuel cost) and the environmental problems it causes.

One of the solutions that can solve this problem and allows them to enjoy the benefits of both modes of transport (common and individual) and reduce their disadvantages is sharing private cars. The private car sharing service is Dial a Ride Problem (DARP) service. Relatively poorly known by the general public and rather neglected by the carriers, the transport on demand dates from the 1970s in the countries of the north, made their appearance since the late 1990s, thanks to the advent information technology and communication.

In this mode of transport, customers (travellers) send a request for transport to an operator including the pickup location (origin), the final destination, the number of people to be transported and the desired passage time [5]. The DARP is to develop vehicle tours to meet transport demands by minimizing the costs of these tours (distance travelled, service time, number of vehicles used), providing good quality of service to travellers (time windows, number of stations visited, etc.) and environment impact.

The DARP is motivated by the fact that individuals are looking for more flexible means of transport that are closer to their expectations. The DARP makes it possible to respond to these expectations. Indeed, it is considered a mode of collective transport, individualized and activated on demand. The DARP offers a better quality/cost of service. Figure 1 shows the repartition of some know DARP in Saharan countries and positioning of Taxi “woro-woro”

Figure 1. Positioning of DARP different modes of transport according to privacy and transport cost criteria.

transport problem according to privacy and cost criteria. Knowing that the cost of operation is related to the quality of service offered, the designers of such a system must find a compromise between these two criteria.

The cost of operation and the quality of service offered to users increases with the number of vehicles commissioned. The fight against pollution is an argument in favour of the DARP since the optimization of the routes and the regrouping of the travellers make it possible a potentially significant savings by rolling vehicles and therefore emissions of air pollutants.

Based on the characteristics of demand nodes for DARP, Douglas et al. [6] and Sin et al. [7] and Yves Molenbruch et al. [8] consider that the DARP can be categorized into two different kinds of problems: static DARP and dynamic DARP. In the static DARP, all demands know in advance. According to the information of the given demands, the dispatcher could design appropriate routes and schedules to serve customers under the specific objective function. In contrast with the static DARP, the dynamic DARP only knew partial information on the demands and the real-time demands might reveal during the vehicle routing. The dispatcher must redesign the vehicle routes and service sequences to handle the real-time demands. Yves Molenbruch et al. [8] surveyed several academic studies for DARP and classified DARP according to the number of vehicles and the characteristics of the demands. In terms of the number of vehicles, the DARP can be classified into the single-vehicle DARP and multi-vehicle DARP.

3. The Dial-a-Ride Problem in Sub-Saharan Countries: The Case of the Cote d’Ivoire

In the countries of sub-Saharan Africa, in recent years, a particular mode of transport, between the taxi and the public transport has emerged: they are commonly called woro-woro [9] in Ivory Coast. It is actually a disorganized highly dynamic demand transport system. We propose in this article a formalized model of this problem in order to organize this sector. A woro-woro with the characteristic of being on a given line: it starts from a point A (departure station) to a point B (arrival station). It performs a stop set according to the customer’s request: either to take a customer, or to get off. Since some years since the relative density of the road network, the itineraries become more and more variable. In this context, a user aims to have a better quality of services, including minimizing travel time and minimizing the distance travelled. The goal of the carrier is to maximize income by minimizing the costs of the distance travelled and time. The disorganization of the sector is the cause of a large number of problems in the field of passenger transport. In recent years, application-based transport and Tourist Vehicle with Driver demand systems (Yongo and others) have been developed. These systems have the advantage of being organized.

4. Dial-a-Ride Approach for “Woro-Woro” System Model

The literature in the particular sense of DARP in Saharan countries is not enormous. Although, this one has been discussed and describe by some authors like Christoffel Venter and Mathetha Mokonyama [10] who present DARP in South Africa Cape Town.

In the particular case of Côte d’Ivoire “woro-woro” system, we can describe as shown in Figure 2, the problem as follows: we consider a company A having a not identical fleet of “woro-woro”, arranged in a set of stations. We also consider a collection of pickup station and a collection of drop-off station. Management of company a fleet of “woro-woro” is entrusted to a manager B. The manager B must respond to a set of transport requests.

Regardless of the problem above, it must address a vehicle scheduling problem that consists of a set of known transport demands defining a vehicle demand allocation and the scheduling of requests for each vehicle.

The problem studied in this section consists of defining a route scheduling (or transport request) characterized by a fixed origin, a destination, a duration and a fixed time windows. These requests and a finite heterogeneous number of vehicles that can be used are defined. Between each trip the duration is known. The desired route scheduling aims to respect time windows and minimize the distance and time cost. In addition, a number of constraints must be satisfied such as:

- All requests for transport are satisfied;

- Each vehicle used in the solution departs from the departure station and covers a set of compatible journeys (in terms of start time) before returning to the depot;

- The carrier has a limited fleet of vehicles.

The first formulation of this planning problem was given by Dantzig et al. [11] for an application in the field of maritime transport. Since then, a set of authors

Figure 2. Graphical description of situation.

has been interested in different specifications of the problem, especially those related to the management of real-life issues [12]. Its application was subsequently extended to various areas such as door to door service. Carlos et al. [13] present a modelling of this problem in the context of the transport of people in special case of non-shared taxi.

A transport request from a collection point (element of the set P) to a delivery point (element of the set D). Serving a request is to pick up a $l_i$ number of people at the point i (taking into account the availability of places) and deposit them in $i+n$ ; we have $l_{i+n}=l_i$ . Thus, people from the same place for different destinations or with different time windows are modeled by different requests. There is a fleet of K vehicles, deposits with capacities $C_k$ . The pickup in i must start in the time window $\left[a_i,b_i\right]$ and the delivery must start in the time window $\left[a_{i+n},b_{i+n}\right]$ . These time windows are deduced from the customer request (i.e. arrival deadline) and the maximum allowed period (percentage of the journey time of the shortest path). This brings us back to a standard m-PDPTW problem. Vehicles leave empty, $l_{ok}=0$ . Travel times $t_{ij}$ between two points (pickup, delivery, deposit) are known. We thus define a complete graph ( $A=V^2$ ) oriented $G=\left(V,A\right)$ doubly valued, where V is the set of collection points, delivery and deposits $\left(V=P\cup D\cup ok|k\in K\right)$ . The arcs $\left(i,j\right)$ are weighted by the values $d_{ij}$ for the distance and $t_{i,j}$ for the time. To determine whether the tour of vehicle k passes through the arc $\left(i,j\right)\in A$ , we use the decision variable $X_{i,j,k}$ whose value is set to 1 if the arc is taken and 0 otherwise. The variable $TIM{E}_i$ represents the moment when the vehicle starts the service in $i\in V$ .

The woro-woro demand transport problem (2WDTP) is a one-level decision problem with $x\in X\subseteq N^n,time\in TIME\subseteq R^u$ and formulated as follows:

$\underset{t}{\min }f\left(time,x\right)$ (1)

$g\left(time,x\right)\le 0$ (2)

In more detail, our one-level problem is formulated mathematically as follows:

$\underset{t,x}{\min }{\displaystyle \underset{\begin{array}{c}i,j\in V\\ k\in K\end{array}}{\sum }\left(d_{ij}+t_{ij}\right)X_{i,j,k}}$ (3)

${\displaystyle \underset{\begin{array}{c}k\in K\\ j\in D\cup ok\end{array}}{\sum }{X}_{j,i,k}}=1\forall i\in P$ (4)

${\displaystyle \underset{j\in D\cup ok}{\sum }{X}_{j,i,k}}-X_{i,n+i,k}=0\forall i\in P,k\in K$ (5)

${\displaystyle \underset{i\in P\cup D\cup ok}{\sum }{X}_{i,j,k}}-{\displaystyle \underset{i\in P\cup D\cup ok}{\sum }{X}_{j,i,k}}=0\forall j\in P\cup D,k\in K$ (6)

$Tim{e}_i+t_{i,j}-M\left(1-{\displaystyle \underset{k\in K}{\sum }{X}_{i,j,k}}\right)-Tim{e}_j\le 0\forall \left(i,j\right)\in A;i,j\ne ok$ (7)

$a_i\le Tim{e}_i\le b_i\forall i\in P\cup D$ (8)

$Tim{e}_i+t_{i,n+i}\le Tim{e}_{n+i}\forall i\in P$ (9)

$l_i\ast X_{i,n+i,k}\le C_k\forall i\in P,k\in K$

$X_{i,j,k}\in \left\{0,1\right\}\forall \left(i,j\right)\in A;k\in K$ (10)

$Tim{e}_i\in R\forall i\in P\cup D$ (11)

Equations (1) and (2) represent a brief mathematical description of our one-level problem. Equation (3) is the problem minimization function. In this part what we are trying to do is to minimize total travel distance and time. Customer satisfaction is taking into account using respect of time windows. Equation (4) ensures the fact that each request is picked. Equation (5) ensures that the next step after a requested pickup is its drop-off point. Equation (6) is the constraint for the respect of vehicle flow at each node. Equation (7) ensures coherence of each trip and prohibition of sub-turns. The constraints (8) ensure respect of time windows. It is the same vehicle that makes the pickup and drop-off. (9) arrived time at a request pickup node is all time inferior than the one of this point drop-off node. Variable definition constrains are done in (10) and (11).

Variable (10) verify if the path (i,j) is yes or not travel by the vehicle k.

Variable (11) contain the request i handling time.

5. Instances Generation

Access to good benchmark instances is always desirable when developing new algorithms, new constraint models, or when comparing existing ones. Hand-written instances are of limited utility and are time-consuming to produce. In this section, we present an algorithm for generating instances for 2WDTP Problem. The generator specification is itself parameterized by a number of integer parameters. The idea of the below algorithm consists to take some input parameters such as the routing area axis and ordinate length and design a referential (OIJ) in the plan and create randomly in this one a set of requests taking into account drop-off and pickup node and also request load. Relative to the number of requests, we also generate a number of vehicles with the associated depot and capacities. In addition, we also calculate travel time and Euclidian distance associate to each arc.

6. MIP-Algorithm Approach Result for 2WDTP Model

The 2WDTP appears both as a DARP problem (Dial A Ride Problem) because it concerns a customer requesting to be transported by a “Woro-Woro” taxi. But also, as a PDP problem (Pickup and Delivery Problem) because they ask to satisfy the customer, in addition to his pickup and his drop-off. This problem has been shown to be NP-hard [14].

Problem resolution will be done exactly using Mix Integer Program of IBM’s CPLEX Optimization Studio 12.8 and its Java API. The tests are conducted under Windows 10 operating system from a computer with a core i7 processor with 4 cores of 3.4 GHz, 8 logical processors and 16 gigs of RAM.

We will also generate instances with a reasonable number of requests (05 ≤ R ≤ 16), vehicles (02 ≤ K ≤ 07) and depot nodes (01 ≤ ok ≤ 04), following our instance generation algorithm. And this in accordance with the complexity of our problem and the fact that we use an exact approach.

As shown in Table 1, our model has been tested using several instances regrouped by increasing stage relative to the number of requests. These instances have been generated using our previous showing instance generation algorithm. In truth this one permits us to have various instances with nodes having no similar properties.

Table 1. Computational result according to each instance generated.

|N|=|PUD|;|ok|=number of depots;|R|=number of requests;|K|=number of vehicles;|Rij|=stage “i”instance “j”and each stage regroup several instances characterise by a same number of requests to handle.

Showing the result table, the main idea is that the resolution average time, increase exponentially follow the number of instances. But sometimes as the can see with instance R5d, the resolution time can be lower than expected due to this instance node configuration.

7. Conclusion

Routing of people presents enormous challenge and crucial operation decision, particularly in Saharan countries. Also, besides this, find and apply the mathematical approach that answers to this issue turn out to be delicate. In this paper, we implement a DARP approach close to a PDP applied to the “Woro-Woro” sector in Ivory Coast. This one appears as a good alternative taking into account the design of precise route with optimal reducing of traveling cost and also a better organization of the transport in this sector. On the other hand, the MIP resolution approach used in this article shows us the limit of exact method due to the expensive resolution time in case of large instance. The next step will be to design a heuristic approach and also think about including dynamic requests.

NOTES

¹Woro-woro are a kind of taxy with common use.

²Djouladlai is a local common name given to people with lot of woro-woro vehicles.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Aloko-N’Guessan, J. (1999) Taxis “WORO-WORO” à ABIDJAN et résonance communale à KOUMASSI.
[2]	Paolo D., Francesco, P. and Manrique de, G.Z.L. (2017) A Multi-Depot Dial-a-Ride Problem with Heterogeneous Vehicles and Compatibility Constraints in Healthcare. Omega, 70, 1-14. https://doi.org/10.1016/j.omega.2016.08.008
[3]	Toth, P. and Vigo, D. (2002) The Vehicule Routing Problem. Society for Industrial and Applied Mathematics, 44, 1-17. https://doi.org/10.1137/1.9780898718515
[4]	Ministry of Construction, Housing, Sanitation and Urban Development (MCLAU) and Japan International Cooperqtion Agency (2015) Urban Transport Master Plan for Greater Abidjan. 3, 13-67. https://openjicareport.jica.go.jp/pdf/12230611_01.pdf
[5]	Brackers, K. and Kovacs, A.A. (2016) A Multi-Period Dial-a-Ride Problem with Driver Consistency. Transportation Research Part B Methodological, 94, 355-377. https://doi.org/10.1016/j.trb.2016.09.010
[6]	Santos, D.O. and Xavier, E.C. (2015) Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive. Expert Systems with Applications, 42, 6728-6737. https://doi.org/10.1016/j.eswa.2015.04.060
[7]	Ho, S.C., Szeto, W.Y., Kuo, Y.-H., Leung, J.M.Y., Petering, M. and Tou, T.W.H. (2018) A Survey of Dial-a-Ride Problems. Transportation Research, 1, 395-421.
[8]	Molenbruch, Y., Braekers K. and Caris, A. (2017) Typology and Literature Review for Dial-a-Ride Problems. Annals of Operations Research, 259, 295-325. https://doi.org/10.1007/s10479-017-2525-0
[9]	Kassi, I. (2007) Régulations des transports populaires et recomposition du territoire urbain d’Abidjan. https://tel.archives-ouvertes.fr/tel-00177509
[10]	Venter, C. and Mokonyama, M. (2001) A Comparison of Two Accessible Transport Service Designs in South Africa. CSIR, South Africa.
[11]	Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M. (1954) Solution of a Large-Scale Traveling Salesman Problem. Operations Research, 2, 365-462. https://doi.org/10.1287/opre.2.4.393
[12]	Tellez, O., Vercraene, S., Lehuéfé, F., Péton, O. and Monteiro, T. (2018) The Fleet Size and Mix Dial-a-Ride Problem with Reconfigurable Vehicle Capacity. Trans- portation Research Part C, 91, 99-123. https://doi.org/10.1016/j.trc.2018.03.020
[13]	Archetti, C., Feillet, D. and Speranza, G. (2015) Complexity of Routing Problems with Release Dates. European Journal of Operational Research, 247, 797-803. https://doi.org/10.1016/j.ejor.2015.06.057
[14]	Daganzo, C.F. and Ouyang, Y.F. (2019) A General Model of Demand-Responsive Transportation Services: From Taxi to Ridesharing to Dial-a-Ride. Transportation Research Part B: Methodological, 126, 213-224. https://doi.org/10.1016/j.trb.2019.06.001