# Investigating Alternative Routes for Employee Shuttle Services Arising in a Textile Company: A Comparative Study

İbrahim Miraç Eligüzel, Nur Sena Yağbasan, Eren Özceylan

► To cite this version:

İbrahim Miraç Eligüzel, Nur Sena Yağbasan, Eren Özceylan. Investigating Alternative Routes for Employee Shuttle Services Arising in a Textile Company: A Comparative Study. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.68-76, 10.1007/978-3-030-85914-5_8. hal-03897892

HAL Id: hal-03897892

https://inria.hal.science/hal-03897892

Submitted on 14 Dec 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Investigating Alternative Routes for Employee Shuttle Services Arising in a Textile Company: A Comparative Study

İbrahim Miraç Eligüzel[0000-0003-3105-9438], Nur Sena Yağbasan[0000-0003-4782-7518] and Eren Özceylan[0000-0002-5213-6335]

Industrial Engineering Department, Gaziantep University, 27100, Gaziantep, Turkey
miraceliguzel@gmail.com, erenozceylan@gmail.com

**Abstract.** For the big companies, picking up a number of employees from various places (residential areas or common places) within a neighborhood and brought to the factory should be a challenging task. Potential improvements for this constantly repeated service planning may result in cost and total traveled distance reduction. To search and provide the aforementioned potential savings, three different scenarios with three different bus capacities are generated for a textile company in this paper. In the first scenario that is also the current application of the company, an integer programming model for the capacitated vehicle routing problem (CVRP) is applied. In this scenario, shuttle buses with a certain capacity are routed by picking up the employees from their homes. In the second scenario, the employees are clustered (cluster size is equal to the vehicle capacity) using P-median model to minimize the total walking distance of employees to the meeting point, then the shuttle buses are routed by visiting the clustered zones (meeting points). In the last scenario, the employees are clustered using K-means model and then, shuttle buses transport workers to factory from the center points of each cluster. Three scenarios with different bus capacities (20, 30 and 50 people) are applied to a textile company (the depot) that includes 1,361 employees. The models are run using Gurobi 9.1.1 with Python 3.8 and the results are discussed. According to the results, second and third scenarios reduce the total traveled distance by 46.90% and 44.10% (averagely) compared to the first scenario, respectively.

**Keywords:** Employee Shuttle Services, Vehicle Routing Problem, P-median, K-means, Clustering.

## 1 Introduction

Service planning of workers between factory and their homes are required to be managed efficiently and effectively in order to reduce costs. Therefore, our motivation in this study can be considered under service routing due to its crucial part in the operation of businesses.
As a solution approach, CVRP is taken into consideration. CVRP is one of the main problems in logistics management aims to generate routes to visit all nodes and turn back to the initial node with pre-decided capacities. CVRP also can be applied on shuttle routing to gather people for carrying them to point of arrival. For instance, school bus routing is solved by CVRP and 28.6% travel cost saving is managed [1]. In that aspect, another study focuses on picking students from the eight points with eight buses on campus via solving with genetic algorithm [2]. Results indicate that shorter distance for two routes is achieved and savings in the distance becomes greater with respect to the total distances. In addition, CVRP is utilized on problem required for associated costs with touristic distribution networks of low demand by solved with genetic algorithm [3]. There are also studies which concern real-life applications; for instance, pharmaceutical and herbalist product delivery [4], waste collection [5], and office furniture delivery [6]. All in all, CVRP can be used for reducing the transportation cost to deliver people to the destination.

Facilities with a large number of workers should use analytic tools to reduce worker picking costs. Therefore, CVRP integration with different approaches can be utilized as another solution method for the facilities which have a large amount of work to provide cost reduced and effective carrying model. From this point of view, workers can be clustered with respect to their home addresses, and routes for vehicles can be decided to gather workers from the center point of each cluster. In literature, there are several studies that consider the clustering before applying routing by aiming more effective solution. One of the studies proposed a method that consists of two mainframes as clustering and optimization and results demonstrate that node clustering before applying CVRP effectively reduces the problem space which leads to quick convergence to the optimum solution [7]. In this aspect, clustered VRP is conducted, in which two exact algorithms, a branch and cut as well as a branch and cut and price is applied, and computational performance is significantly improved [8]. Another instance of study in the aforementioned perspective presents the algorithm integrates the Bat algorithm with a modified K-means clustering, which is based on clustering first route second to convert the original VRP into traveling salesman problems with reduced complexity [9]. In addition to the aforementioned studies with clustering and CVRP, there are several studies in literature such as using K-means with the cheapest link algorithm for routing the Indian cooperative dairy distribution network [10], K-means with grey wolf algorithm [11], and recursive K-means with Dijkstra algorithm [12].

For the applied methods, some assumptions are made. One of them is the there is no traffic density during the service operation. Secondly, whole considered vehicles and workers expected to travel at the same speed. Therefore, elapsed times are assumed to be proportional to distances.

In this study, service problem is handled under three scenarios and compared with each other for picking workers from their home addresses. Also, for each scenario, three different capacity variants are considered, which are decided as 20, 30, and 50 people.

Three solution scenarios in this study are explained as follows. In the first scenario, CVRP is solved by linear programming without clustering for collecting workers
from their home addresses. In the second scenario, the P-median method is applied to
cluster the addresses and gather central addresses for each cluster. Distance between
connected nodes and their centers are obtained to calculate walking distance. Then,
distances between centers and facilities are summed to have total distances for trans-
portation. Therefore, total walking distance minimization is accomplished and trans-
portation cost is reduced. Lastly, K-means is applied to cluster home addresses to
minimize walking distance and obtain the center point for each cluster. After that, the
distance between each center and factory is calculated and summed, and then the
walking distance (objective value of K-means) is added to the total distance between
centers and factory. Mentioned three scenarios are illustrated in Fig. 1. For each
aforementioned method, three different capacities are concerned. The paper is orga-
nized as follows: Section 2 formally defines the applied methodologies. Input data
and the solution of the three scenarios are discussed in Section 3. Finally, the last
section presents our conclusions.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Representation of the considered three scenarios</figcaption></figure>

2 Methodologies

As mentioned in the previous section, three different scenarios are considered in this
study. To generate the scenarios, three different models namely CVRP, P-median, and
K-means are used and described below.

## 2.1 Capacitated Vehicle Routing Problem

CVRP refers to a class of problems in which a series of routes for a fleet of vehicles located at one depot must be calculated for a number of geographically scattered customers, and the vehicles must have the maximum loading capacity. CVRP's goal is to reduce overall cost (i.e., a weighted function of the number of routes and their travel distance) while serving a group of customers with known needs. CVRP is a one of the well-known combinatorial problems that belongs to the NP-Hard problem set [13]. Let $G = (V, E)$ be a directed graph with vertices $V = \{0, 1, ..., n\}$ and edges $H = \{(i,j): i, j \in V, i \neq j\}$. The depot is represented by vertex 0, and each remaining vertex $i$ represents a customer with a positive demand $d_i$. There is a fleet of $p$ vehicles
with the same capacity $Q$. The non-negative cost/distance $c_{ij}$ is associated with each arc $(i, j) \in H$. The minimum number of vehicles needed to serve all customers is $\sum_{i=1}^{n} d_i/pQ$. $x_{ij}$ takes value 1 if edge belongs to the optimal solution, and value 0 otherwise, $\forall i, j \in V: i \neq j$. $u_i$ is an additional continuous variable representing the load of the vehicle after visiting customer $i$ [14]. The mathematical formulation which is used in this study is described below [15].

Objective function

$$ \text{Min} \sum_{i=0}^{n} \sum_{j=0}^{n} x_{ij}c_{ij} \qquad (1) $$

Subject to

$$ \sum_{i \in V} x_{ij} = 1 \qquad \forall j \in V \qquad (2) $$

$$ \sum_{j \in V} x_{ij} = 1 \qquad \forall i \in V \qquad (3) $$

$$ \sum_{i \in V} x_{i0} = p \qquad (4) $$

$$ \sum_{j \in V} x_{0j} = p \qquad (5) $$

$$ u_i - u_j + Qx_{ij} \leq Q - d_i \qquad \forall i, j \in V, i \neq j \qquad (6) $$

$$ d_i \leq u_i \leq Q \qquad \forall i \in V \qquad (7) $$

$$ x_{ij} \in \{0,1\} \qquad \forall i, j \in V \qquad (8) $$

The CVRP consists of finding a collection of simple circuits (corresponding to vehicle routes) with minimum cost, defined as the sum of the costs of the arcs belonging to the circuits (Eq. 1). Constraints (2) and (3) (indegree and outdegree of nodes) impose that exactly one edge enters and leaves each vertex associated with a customer, respectively. Analogously, Constraints (4) and (5) ensure the degree requirements for the vertex of depot. Constraints (6) and (7) impose the capacity requirements of CVRP while eliminating the sub-tours [16]. Finally, Constraint (8) is the integrality conditions.

## 2.2 Capacitated P-median Approach

The P-median model is applied to minimize the employees' total walking distance to the meeting point by clustering the employees. Due to a limited capacity of clusters, capacitated P-median on a discrete space is considered in this study. The capacitated P-median problem seeks to define the number of P candidate facility (clusters) to be opened, and which customers (employees) will be assigned to each facility (cluster). In the model, every cluster has a limited employee capacity and each employee has one demand. The problem should consider that each cluster can serve only a limited number of demands so that the sum of distances between each demand point (employee home) and the facility (cluster center) assigned to that demand point is minimized. In the model, $i$ and $j= 1, 2, ..., n$ is the set of employees and also of possible medians where P clusters will be located, $d_i$ is the demand of employee $i$, $Q_j$ is the capacity of the median (cluster) $j$, $d_{ij} > 0$ ($i \neq j$) is the distance between employee $i$ and cluster median $j$. $x_{ij}$ is a binary decision variable that takes 1 if an employee $i$ is assigned to a cluster $j$, otherwise it is 0. $y_j$ is also a binary decision variable that takes 1 if an employee is selected as a cluster median $j$, otherwise it is 0. The problem for-
mulation is given as follows [17]:

$$ \text{Objective function} \\ \text{Min} \sum_{i}^{n} \sum_{j}^{n} x_{ij}d_{ij}d_{i} \qquad (9) $$

$$ \text{Subject to} \\ \sum_{j} x_{ij} = 1, \forall i, \qquad (10) $$

$$ \sum_{j} y_{j} = p, \qquad (11) $$

$$ x_{ij}d_{i} \le Q_{j}y_{j}, \forall i,j, \qquad (12) $$

$$ x_{ij}, y_{j} \in \{0, 1\}. \qquad (13) $$

The objective function (Eq. 9) aims to minimize total walking distance of all employees. Constraint (10) imposes that each employee is assigned to one and only one cluster median, Constraint (11) guarantees that *P* cluster medians are selected, Constraint (12) forces that a total median capacity to be respected and Constraint (13) prepares the binary integer conditions.

## 2.3 Capacitated K-means Approach

Capacitated K-means is also applied to cluster the employees. The capacitated K-means approach seeks to define *K* amount candidate cluster centers to be decided and which employees will be assigned to each cluster center while employees attended to nearest the cluster center. The capacitated K-means problem formulation is given as follows [18]:

$$ \text{Objective function} \\ \text{Minimize} \sum_{i=1}^{n} \sum_{h=1}^{k} T_{i,h} * \left( \frac{1}{2} (x_i - \mu_{h,t})^2 \right) \qquad (14) $$

$$ \text{Subject to} \\ \sum_{i=1}^{n} T_{i,h} \ge \tau_{h}, \quad h=1, 2, \dots, k \qquad (15) $$

$$ \sum_{h=1}^{k} T_{i,h} = 1, \quad i = 1, 2, \dots, n \qquad (16) $$

$$ T_{i,h} \ge 1, \quad i = 1, 2, \dots, n, \quad h = 1, 2, \dots, k \qquad (17) $$

where, Given a database *X* of *n* points, minimum cluster membership values $\tau_h \ge 0$, $h = 1, \dots, k$ and cluster centers $\mu_{1,h}, \mu_{2,h}, \dots, \mu_{k,h}$ at iteration *t*. $T_{i,h}$ is binary variable that demonstrates attendance of data point $x_i$ is to nearest center $\mu_h$ or not [18]. Objective function (14) aims to attend nodes to its nearest cluster center. Constraint (15) ensures the attendance of minimum number of nodes to one cluster. Constraint (16) ensures that one node is allowed to attend just one cluster center and constraint (17) forces all nodes to attend cluster.

# 3 Case Study and Results

The service plan of Kartal carpet, which operates in Gaziantep province, is taken into consideration. Utilized case comprehends the 1,362 nodes (including the factory) with its GPS coordinates and GPS coordinates converted into longitude and latitude values
in order to gather nodes' positions in X-Y axis. After gathering X-Y axis, the distance matrix is generated by utilizing Euclidian distance. For instance, "a1" has longitude and latitude "37.1383, 37.3716" values. Distance between "a1" and "a2" (37.0898, 37.3676) is calculated by Euclidian distance and it is equal to 4.86km. Normally, there are three shifts for workers per day. However, the picking of workers for only one shift is focused on in this paper. The geographical locations of 1,362 nodes in terms of X-Y values from the GPS coordinates are shown in Fig. 2.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Illustration X-Y coordinates of home addresses in Gaziantep providence</figcaption></figure>

The aforementioned three methods, which are P-median, K-means and CVRP, are applied by using Python 3.8- Gurobi 9.1.1 with the time limit set to three hours with a computer that has Intel Core i7 9750H CPU with 8GB RAM features. Capacities of vehicles are selected as 20 (e.g. VW Crafter), 30 (e.g. Isuzu Turkuaz) and 50 (e.g. Mercedes - Benz Tourismo). The number of routes and clusters is decided by the total number of workers divided by capacities and decimals are rounded up which are 69 (20 capacity), 46 (30 capacity) and 28 (50 capacity). For instance, if a bus with 30 people capacity is chosen, and then scenario#1 has to visit 1,361 workers with 46 routes/buses. Scenario#2 and #3 divide 1,361 workers into 46 (1,361/30) clusters then the buses have to pick 30 workers from each cluster then back to the factory.

<table><caption>Table 1. Results of the three methods (in meters)</caption><thead><tr><th>Capacity</th><th>Scenario</th><th>Total Walking Distance</th><th>Average Distance per Worker</th><th>Total Bus Distance</th><th>Average Distance per Bus</th><th>Total Distance</th></tr></thead><tbody><tr><td rowspan="3">20</td><td>#1</td><td>0.00</td><td>0.00</td><td>118,900.00</td><td>1,723.19</td><td>118,900.00</td></tr><tr><td>#2</td><td>5,305.70</td><td>3.89</td><td>56,900.00</td><td>824.63</td><td>62,205.70</td></tr><tr><td>#3</td><td>4,984.00</td><td>3.66</td><td>58,700.00</td><td>850.70</td><td>63,684.00</td></tr><tr><td rowspan="3">30</td><td>#1</td><td>0.00</td><td>0.00</td><td>82,700.00</td><td>1,797.83</td><td>82,700.00</td></tr><tr><td>#2</td><td>5,762.70</td><td>4.23</td><td>38,600.00</td><td>839.10</td><td>44,362.70</td></tr><tr><td>#3</td><td>3,639.50</td><td>2.67</td><td>38,555.10</td><td>838.20</td><td>42,194.60</td></tr><tr><td rowspan="3">50</td><td>#1</td><td>0.00</td><td>0.00</td><td>55,700.00</td><td>1,989.29</td><td>55,700.00</td></tr><tr><td>#2</td><td>4,131.00</td><td>3.03</td><td>25,540.00</td><td>912.10</td><td>29,671.00</td></tr><tr><td>#3</td><td>9,546.30</td><td>7.01</td><td>24,258.40</td><td>866.40</td><td>33,804.70</td></tr></tbody></table>
In Table 1, the feasible results of three scenarios are given. From Table 1, it can be easily said that clustering the home addresses with capacitated P-median (scenario#2) and transporting workers to the factory from the obtained centers (clusters) outstandingly reduces the total distances compared to CVRP application (scenario#1). When it comes to capacitated K-means (scenario#3), it demonstrates better performance for capacity with 30 people compared to the other two scenarios. On the other hand, the capacitated P-median gives a better result than the application of capacitated K-means for the capacity of 20 and 50 people. From the general view, there is a significant difference between capacitated P-median and K-means approaches. Capacitated P-median outperforms the capacitated K-means by 1.48 km and 4.13 km with capacities 20 and 50, respectively. However, capacitated K-means shorten the distance by 2.17 km compared to the capacitated P-median. As a result, the minimum total distance is obtained by scenario2# with a capacity of 50. When average walking distance per worker is taken into consideration, the minimum distance is gathered by application of scenario3# with a capacity of 30. Lastly, if the average distance per bus is aimed, the best result is obtained by applying scenario2# with the capacity of 20. Therefore, decision-makers are able to select the best alternative with respect to their objectives.

# 4 Conclusion

In the proposed study, three methods are utilized in order to minimize the total distances to carry workers to the factory. Three different scenarios are considered and generated. In the first scenario, without clustering, 1,361 workers are picked with a CVRP model. In the following two scenarios, 1,361 workers are clustered using capacitated K-means and P-median approaches, and then the buses are directed to the cluster centers. All three scenarios are run with three different vehicle capacities as 20, 30 and 50. Because of the problem size, a time limit is considered and feasible solutions are obtained. Results demonstrate that the total distance (vehicle distance + walking distance) decreases with the increments in capacity. However, capacitated P-median and K-means show different performances with respect to given capacity and CVRP has the longest total distance for all three scenarios. The minimum total distance is obtained when the workers are clustered with P-median and 50 people capacitated bus is used. On the other hand, clustering with the K-means approach with 30 people capacitated bus yields the minimum total walking distance. As an extension of this paper, the authors will focus on the simultaneous application of VRP and clustering approaches rather than the hierarchical approach. In addition, the problem will be handled as a bi-level programming where the upper and lower levels are represented by the company and workers, respectively. Finally, traffic congestion that affects the traveling time will be considered to reflect the real-life dynamics.

# References

1. Bektaş, T., and Seda Elmastaş. Solving school bus routing problems through integer programming. Journal of the Operational Research Society, 58 (12), 1599-1604. (2007).
2. Mohammed, Mazin Abed, et al. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of computational science, 21, 255-262 (2017).

3. Medina, Josep R., and Víctor Yepes. Optimization of touristic distribution netwoorks using genetic algorithms. SORT: statistics and operations research transactions, 27 (1), 0095-112 (2003).

4. Fischetti, Matteo, Paolo Toth, and Daniele Vigo. "A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs." Operations Research 42.5, 846-859. (1994).

5. Franca, Luíza Santana, Glaydston Mattos Ribeiro, and Gisele de Lorena Diniz Chaves. "The planning of selective collection in a real-life vehicle routing problem: A case in Rio de Janeiro." Sustainable Cities and Society 47, 101488. (2019).

6. Kır, Sena, Harun Reşit Yazgan, and Emre Tüncel. "A novel heuristic algorithm for capacitated vehicle routing problem." Journal of Industrial Engineering International 13.3, 323-330. (2017).

7. Abdillah, Ubassy, and Suyanto Suyanto. Clustering Nodes and Discretizing Movement to Increase the Effectiveness of HEFA for a CVRP. International Journal of Advanced Computer Science and Applications (IJACSA), 11(4), 774-779. (2020).

8. Battarra, Maria, Güneş Erdoğan, and Daniele Vigo. Exact algorithms for the clustered vehicle routing problem. Operations Research, 62(1), 58-71. (2014).

9. Kassem, Sally, et al. A hybrid bat algorithm to solve the capacitated vehicle routing problem. 2019 Novel Intelligent and Leading Emerging Sciences Conference (NILES). Vol. 1. IEEE, (2019).

10. Rautela, Anubha, S. K. Sharma, and P. Bhardwaj. "Distribution planning using capacitated clustering and vehicle routing problem." Journal of Advances in Management Research (2019).

11. Korayem, Lamiaa, M. Khorsid, and S. S. Kassem. "Using grey wolf algorithm to solve the capacitated vehicle routing problem." IOP conference series: materials science and engineering. 83. 1. IOP Publishing, (2015).

12. Moussa, Hassan. "Using Recursive K-Means and Dijkstra Algorithm to Solve CVRP." arXiv preprint arXiv:2102.00567 (2021).

13. Lin, Shih-Wei, et al. Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 36 (2), 1505-1512 (2009).

14. Borcinova, Zuzana. Two models of the capacitated vehicle routing problem. Croatian Operational Research Review, 463-469. (2017).

15. Toth, Paolo, and Daniele Vigo. Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123, 487-512. (2002).

16. Fischetti, Matteo, Paolo Toth, and Daniele Vigo. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operations Research, 42 (5), 846-859. (1994).

17. Shamsipoor, Hengameh, Mohammad Ali Sandidzadeh, and Masoud Yaghini. Solving Capacitated P-Median Problem by a New Structure of Neural Network. International Journal of Industrial Engineering, 19(8). (2012).

18. Demiriz, Ayhan, Kristin P. Bennett, and Paul S. Bradley. "Using assignment constraints to avoid empty clusters in k-means clustering." Constrained clustering: advances in algorithms, theory, and applications, 201. (2008).