{'fraction_non_alphanumeric': 0.02719174871073605, 'fraction_numerical': 0.006250976715111736, 'mean_word_length': 4.72255756762799, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Development of an Approximation Algorithm for the Vehicle Routing Problem with Operating Time Constraints

This study investigates vehicle operating time as a constraint within the vehicle routing problem (VRP) with multiple trips (VRPMT). In the basic VRP, a single route is assigned to each vehicle and the solution must satisfy both the load and distance (or travel time) constraints. However, in the real-world problem, one vehicle is assigned to multiple routes per day. Since this becomes a large-scale combinatorial optimization problem, it becomes difficult to find an exact solution. Therefore, in previous research, a heuristic method using a two-phase algorithm was proposed. However, since the precision of the two-phase algorithm is greatly influenced by the solution selected for the first phase, selection of solutions in this phase is crucial. In this study, the advantages of the oneand two-phase methods are integrated in a new proposed method.


Introduction
The vehicle routing problem (VRP) poses the challenge of finding an optimal solution for visiting a set of customers using multiple vehicles under various constraints [1]. The solution of this standard combinatorial optimization problem is also extremely practical and has a variety of applications such as postal and newspaper deliveries, waste collection, and school-bus scheduling [2].
The distance-constrained VRP expands upon the basic VRP [3] [4]. Recently, environmental issues have become increasingly important to industries and businesses. This requires a distributor to determine how many vehicles of what sizes along which routes will be used to deliver commodities so that the demands of all customers are satisfied within the customers' available time with minimum operating cost. Wang and Chiu [5] developed a model for a distribution center to support decisions for vehicle types and quantities for the VRP with multiple time windows and developed a genetic algorithm for an efficient solution of the optimization problem. Yalcin and Erginel [6] developed an algorithm to solve the VRP with backhauls (VRPB) by using mathematical models. They proposed a new algorithm based on fuzzy multi-objective programming to solve the VRPB. Coelho et al. [7] developed an algorithm inspired by the variable neighborhood search metaheuristic for the single VRP with deliveries and selective pickups. In this problem, a single route is assigned to each vehicle and the solution must satisfy both the load and distance (or travel time) constraints. However, in the real-world problem, a single vehicle is assigned to multiple routes per day.
This study investigates the vehicle operating time as a constraint within VRP with multiple trips (VRPMT). This constraint states that the total travel time for a vehicle assigned to multiple routes cannot exceed a specified limit and is equivalent to the single-day-work time constraint on the vehicle s driver. To solve this problem, a multi-phase algorithm was proposed. Fleischmann [8] proposed a two-phase algorithm for VRPMT. In the first phase, he used a modification to the saving algorithm to solve the VRP. Then, he used a bin-packed algorithm to solve the vehicle assignment problem in the second phase. However, the precision of a two-phase algorithm is greatly influenced by the solution selected in the first phase. Even if a better solution is used in the first phase, a high-quality, feasible solution is not necessarily found in the second phase.
Lin and Kwok [9] used a two-objective function with total distance and working time (or distance) balance in the first phase. Taillard et al. [10] proposed the route generation procedure to first produce several good VRP solutions using the Tabu search. This procedure is repeated several times, and some of the generated vehicle routes are selected as candidates for the final VRP solution. Since two or more solutions can be considered in the first-phase, the precision of the solution can increase; however, because this method may be overly complicated and may immediately fall into a local minimum, it cannot reliably produce high-quality feasible solutions. Brandao and Mercer [11] reported a Tabu search heuristic for solving a real-world application where additional characteristics are taken into account. Then, they proposed a streamlined version of their Tabu search heuristic [12] and compared their results with those obtained by Taillard et al. [10]. Conversely, Olivera and Viera [13] applied the twophase solution method of Taillard et al. [10] and repeated the improvement procedure of the first and second phases. They obtained an improvement in search effectiveness of their process by using the infeasible result of a previous second phase for the next first phase. However, the correction of an infeasible solution to obtain a feasible solution involves high computational costs. Cattaruzza et al. [14] proposed an efficient genetic algorithm for the VRPMT. They used a memetic algorithm in which each chromosome defines a customer sequence, and the chromosomes then must be transformed into a feasible VRPMT solution. To achieve this, they proposed an adaptation of the splitting procedure proposed by Prins [15]. Azi et al. [16] proposed an adaptive large neighborhood search (ALNS) to address the VRPMT with time windows. In this algorithm, the destruction operators are first selected at the work-day level, then at the route level, and finally at the customer level.
A capacitated location-routing problem (LRP) is one of the problems that are similar to the VRPMT where a customer's assignment problem and a VRP must be solved simultaneously [17] [18]. Yu et al. [19] have proposed an approximation method for simultaneously solving these two problems by representing a customer's assignment and vehicle routing using a one-dimensional vector. By using this approximation method instead of dividing the optimization procedure into two phases, good solutions could be found. However, a high computational cost was incurred due to the expanded solution space required for concurrently solving a VRP and an assignment problem.
This study investigates the simultaneous optimization of the total distance and the number of vehicles, with the objective of developing an approximation algorithm for the VRPMT. In this study, an approximate method that combines the advantages of the one-phase method of Yu et al. and the two-phase method of Olivera and Viera is proposed. This study uses a one-phase metaheuristic search method with the simplest possible rules to enable flexible application of the method to practical problems with various additional constraints.

Modeling VRP with operating time constraints
Consider a collection VRP with N customers divided among K vehicles. Assume that demand quantity q i for customer i, travel distance C ij (i, j = 0, 1, , N ) between customers i and j, and a load capacity constraint Q for each vehicle are given. All vehicles depart from a depot, denoted as location 0, and return to the same depot at the end of the route. One vehicle is assigned to multiple routes and no vehicle may exceed a daily operating time T in covering the assigned multiple routes. This research ignores shipping and discharging times as they are negligible for every customer. Figure 1 shows a schematic of a VRP involving four vehicles covering four routes. Each custome's demand is shown in parentheses beside the customer number. In this figure, each vehicle is assigned one route. The total demand in each route must not exceed the loading capacity constraint (Q = 15), and the travel time for these routes must not exceed the daily operating time (T = 30). The number in the circle shows the travel distance, and t k shows the operating time of route k. The speed of the vehicles is set to 1. As shown in Fig. 1, when the vehicles are assigned by the optimal solution of VRP, the total distance is 74. However, two or more routes cannot be traveled by one vehicle within operating time constraints such that the number of vehicles forms four sets. Conversely, when vehicles are assigned allowing the total distance to become ≤ 88, the number of vehicles forms three sets and may decrease (see Fig. 2). Therefore, an optimal solution of VRP will not necessarily minimize the number of vehicles. In reality, because of the acquisition and operating costs of the vehicles, the solution must minimize both the number of vehicles and the total distance. Therefore, in this study, we aim to minimize the total travel distance after minimizing the number of vehicles.
Additionally, in the case of the operating time constraint T = 18, routes 2 and 4 shown in Fig. 1 cannot fulfill this constraint and therefore fall into an infeasible solution of the VRPMT. By contrast, each route of Fig. 2 becomes a feasible solution of the VRPMT. This demonstrates that producing a feasible solution of the VRP with operating time constraints from its optimal solution is not necessary.

Formulating VRP with operating time constraints
The formulation of VRP with operating time constraints used in this study is as follows.
(i) Vector representation of travel route Travel routes are represented as N -dimensional vectors with N customers in order and an allocation sequence vector for a total of M routes: where x n refers to the name of the n th customer when all customers in the M routes are arranged in order, (ii) Load capacity constraints For any given routing solution (X, I), the total demand quantity for each route must not exceed the load capacity Q: (iii) Travel distance For any given routing solution (X, I), the travel distance f m (X, I) for the m th route is defined by Thus, the total travel distance F (X, I) is (iv) Vector representation of vehicle allocation Considering the allocation of M routes for K vehicles, the M -dimensional vector consisting of the route numbers and an allocation sequence vector for these vehicles is used to represent the allocation of routes to each vehicle: where r m refers to the route number of the m th route and z k indicates the position of the k th vehicle's final route within the M -dimensional vector R; hereafter, (R, Z) is referred to as the route allocation.
(v) Vehicle operating time constraints The travel time for each vehicle must not exceed a predetermined operating time T per day. We assume that the vehicle speed s is constant and that the following formula applies to each vehicle:

Two-phase algorithm in VRPMT
A diagram of the two-phase algorithm of Lin and Kwok [9] is shown in Fig.3. Lin and Kwok's algorithm of VRPMT using the twophase method generates a solution using a two-alternative valuation scale of the total distance and the distance balance of the routes in the first phase. Conversely, the application of the method of Taillard et al. [10] generated a solution using the distance balance of the routes in the first phase. In the second phase, the assignment of vehicles was performed by applying a bin-packing algorithm for the solution generated in the first phase. Therefore, the first phase of valuation scales will have a significant influence on the second phase.
To evaluate the performance of their algorithm, Lin and Kwok [9] applied the metaheuristics of Tabu search and simulated annealing (SA) on real and simulated data. Their computational tests focused on two areas with high customer density and included a good condition that should be challenged by the solutions obtained by their method. However, potential depots may be located in area boundaries, possibly affecting the result of the tests of this condition.
In this study, the influence of the total distance minimization (optimal solution of VRP) and distance balance of the routes in the first phase on the accuracy of a solution using the benchmark problem (vrpnc1) was evaluated [20]. This was modified by Taillard et al. [10] in order to use it for the VRPMT. Table 1 shows the total distance F and the number of vehicles K with the constraints that the speed of a vehicle is 25 km/hour and the operating time is 8 hours. If the solution obtained in the first phase does not fulfill the operating time constraints, the vehicle number is shown in parentheses. In the case of vrpnc1, since there is a depot at the city center (30, 40), the solution of the total distance minimization and distance balance of routes may be relatively similar. For comparison, we set up a case (0, 0) in which the depot is separate from the city center, and considered the characteristics of the generated vehicle routes, namely the differences in the total travel distance and number of vehicles (see Figs. 4 and 5). Table 1 shows that vehicle routes generated by minimizing the total distance do not necessarily minimize the number of vehicles. Moreover, in the case of a depot located at the origin, even though the number of vehicles was its minimum of five sets, vehicle routes generated by minimizing the total distance generated a solution that was unable to satisfy the operating time constraints. Conversely, when balancing five routes by distance, even for the case where the depot is located at the origin, a good feasible solution had five sets of vehicles. However, the number of vehicles was the minimum when there were six routes with the depot at the center; therefore, while finding solutions with a various numbers of routes is necessary, it is easy to find the case of the minimum number of vehicles when the distance balance of the routes is used. Therefore, when the total distance is minimized after the minimization of the number of vehicles using the distance balance of the routes, it is possible to obtain a better, feasible solution. Therefore, in this study, the distance balance of the routes, i.e., the algorithm of Taillard et al. [10] is used for our algorithm of the VRPMT. In the following section, the metaheuristic search method for improving a solution is proposed.

One-phase algorithm in VRPMT
In this section, the one-phase algorithm is described. This algorithm is the method of simultaneously solving the VRP and the vehicle assignment problem. It is already used in the LRP that is similar to the VRPMT and is streamlined compared with the two-phase algorithm. Since the time required for one iteration is short, in the algorithm of a hierarchical type, this method becomes a very powerful tool.
Yu et al. [19] have proposed a solution expression using a one-dimensional vector that incorporates institutions, cities, and dividing points. In their study, facility location, assignment of cities to vehicles, and routes can be simultaneously changed by choosing three elements of a one-dimensional vector, without distinguishing an institution, city, and dividing point and generating a neighborhood solution. In our research, we applied this method to the VRPMT and searched for the optimal solution using a one-dimensional vector with route division and vehicles divisions in the element. Yu et al. [19] inserted dividing points of the routes into the one-dimensional vector which shows a round route. Moreover, in this research, dividing points of each vehicles are also inserted in a onedimensional vector.

Solution expression for the VRPMT
In a one-dimensional vector, the dividing point of a route is denoted by (0) and the dividing point of vehicles is denoted by (-1). Fig. 2 shows vehicle routing such that vehicle 1 follows routes 1 and 2, vehicle 2 follows routes 3 and 4, and vehicle 3 follows routes 5 and 6. The notation of the one-dimensional vector as follows: The Tabu search was performed in some studies when the VRPMT was treated with their algorithms [10][11][12][13]. By contrast, the LRP algorithm of Yu et al. [19] using the one-phase method generates a solution using the SA method [21,22], and this study uses a one-phase local search method with the simplest possible rules to enable a flexible application to practical problems with various additional constraints. We applied the SA method as the  A new proposed solution X ′ is generated from the current solution X according to the neighborhood structure N (X), and the probability of accepting inferior solution X ′ is determined by the two distances of the solutions X and X ′ and the temperature. During the search, the temperature T j is gradually decreased using the function H, T j+1 = H(T j ). The SA algorithm used here for the minimization problem is summarized as follows.

SA algorithm
1. Set an initial temperature T mp 0 = T 0 , an initial solution X, set the best solution X * = X and iteration j = 0.
2. Select a new solution randomly X ′ ∈ N (X).
In the above algorithm, the setting of a neighborhood structure N (X) and the renewal method H are important issues affecting the performance of the algorithm. Cattaruzza et al. [14] introduced a new local search operator based on the combination of standard VRP moves and swaps between trips. Azi et al. [16] probabilistically chosen a destruction and a reconstruction operator based on their current weights. However, in order to perform these methods efficiently, it is necessary to set up appropriate weight.
In this study, the temperature is set to a constant value (T mp = 1.6) and we use inversion, which is the reversal of the order of elements between positions i and j, for the neighborhood structure. Table 2 shows the total distance and the number of vehicles in the case of using the one-phase algorithm by generating an initial vehicle routing solution in which the distance of the route is balanced. With a depot at the center, the total distance was shortened, minimizing the number of vehicles; however, when the depot was located at the origin, not only the total distance but also the number of vehicles decreased. The above result shows that the one-phase algorithm is an effective method for treatment of small-size problems. However, for a middle-size problem, the convergence of the solution required a very high computational cost.

Modified Two-phase algorithm in VRPMT
Olivera and Viera [13] applied the two-phase algorithm of Taillard et al. [10], where after solving the second phase they return to the first phase and repeat the procedure to improve the solution quality. In this study, the algorithm of Olivera and Viera is used instead of that of Taillard's.
The two-phase algorithm of Olivera and Viera is schematically shown in Fig. 6. At first, the number of vehicles K is set to a sufficiently large value to ensure the feasibility of an initial solution. Next, the VRP is solved using a Tabu search method under the loading capacity constraint in the first phase. In the second phase, route assignment for the vehicles is performed by applying a binpacking algorithm. If this solution is a feasible solution under the operating time constraints, the number of vehicles is decreased, and this algorithm is applied once again. However, in the case that this solution is infeasible, the algorithm is repeated until a terminal condition is satisfied. After solving the second phase the algorithm returns to the first phase and repeats the procedure to achieve an improvement.
In Olivera and Viera's algorithm an adaptive memory approach is used to tackle the VRPMT. After phase 2, each route is labeled with its overtime value. The past data is saved in memory in the order of satisfying the op-Routes assignment to vehicles is performed !Second phase"  Fig. 6 Flow chart of the algorithm of Olivera and Viera [13] erating time constraints. Upon return to phase 1, new VRP solutions are generated by probabilistically selecting the routes in the memory. Moreover, Olivera and Viera considered that a solution could be most efficiently obtained by improving the vehicle parameters that show the highest deviation from the constraint.
To understand the characteristics of one-and twophase methods, we applied the one-phase method for the VRPMT and Olivera and Viera's two-phase algorithm to a 75-cities problem (vrpnc2) [20]. The SA method is used for both algorithms to enable the comparison of the two approaches on the same footing. Table 3 shows the relationship between the number of times that a vehicle is improved and the total distance. Olivera and Viera's twophase method uses the route of vehicles to obtain a value near the operating time constraints in the second-phase to the first-phase. Therefore, although this algorithm reaches a good solution quickly, it may immediately fall into a local optimal solution. Conversely, the one-phase method shows very slow continuous improvement. Hence, an efficient search can be performed if the advantages of both of these methods are combined.

Integration of the advantages of the one-and two-phase methods in VRPMT
In this section, a new method combining the advantages of the one-and two-phase methods is described. These advantages are the change of the selection method of the vehicles to improve the two-phase method and the application of the one-phase method. Fig.7 shows an illustration of the method for selection of the vehicles in Olivera and Viera's two-phase method using The number of vehicle improvements Olivera's algorithm One-phase algorithm a one-dimensional vector. In the second phase, routes are assigned to the vehicles, and the determination of the feasibility of the proposed solution under the loading capacity constraint is performed. Next, vehicles that show the highest deviation from capacity constraint are selected. Then, the algorithm returns to the first phase and improves only the routes of selected vehicles. Since only the routes of the selected vehicles are improved, their method reaches a good solution quickly. However, because the same vehicle is selected in many cases, it is easy to fall into a local optimum.
Therefore, in order to add variability to the two-phase method, we combined random selection with the neighborhood selection. Fig. 8 shows an illustration of our proposed selection method. First, a single vehicle is selected at random. Next, the center of gravity of all the routes included for the selected vehicles is calculated. In this study, the route with a short distance between the centers of gravity is considered to be a route in the neighborhood. Therefore, the vehicle for which a route will be included in the neighborhood is selected. Useless searches can be excluded using routes with the smallest distances. Furthermore, in the proposed method, a one-phase method is used for the improvement of routes in the selected vehicle.
The proposed integrated algorithm is shown in Fig. 9. The basic idea is to search for a better solution by streamlined algorithm of previous research. To compare the performance of the proposed method with those of the other methods, the same benchmark problems (vrpnc1, vrpnc2, and vrpnc3) were used as in previous studies [20]. The SA method is used as the search method and the temperature is fixed to 1.6. Table 4 shows the results for the obtained feasible solutions in each method. In the table, MOD, OV, and TLG refer to the proposed method, the approximate method of Olivera and Viera, and the approximate method of Taillard, respectively. The circles denote that a feasible solution for the number of the minimum vehicles was found.
Inspection of the results in Table 4 shows that when the number of customers is 50, Olivera and Viera's method and the proposed method find that the time for the minimum number of the vehicles is T = 275. When the number of customers is 75, only the proposed method is able to find the total travel time values for the minimum num-old  Fig. 7 Vehicle selection method in the Olivera and Viera s two-phase method

Conclusion
In this study, we developed an approximation algorithm for solving the VRPMT where it is difficult to find a feasible solution given severe vehicle operating time constraints. In this study, the advantages of two previous methods for treating this problem are combined. A capacitated LRP is a problem similar to the VRPMT. Therefore, the one-phase method applied to this problem is modified in order to apply it to the VRPMT. Although the approximate solution could be easily found, this approach involved a high computational cost. In case of the VRPMT solved using a two-phase algorithm, minimizing the total distance in the first phase may minimize the number of vehicles, but may generate an infeasible solution. However, the method of limiting the vehicles for which rescheduling of a proposed route is performed, and obtaining repeated partial improvement was found to be effective. We proposed the method of finding a good, feasible solution by adding diversification to the selection of vehicles. Furthermore, search effectiveness has been improved by selection of vehicles in consideration of the route neighborhood. Conversely, the search is simplified by representing these solutions using a one-dimensional vector. Numerical experiments showed that using the proposed method, we successfully obtained feasible solutions that were unobtainable in previous studies.
In the future, the application of the proposed algorithm to a benchmark problem and a real-world problem and the investigation of the influence of its computational cost and quality of its results will be necessary.
A sequence of two vehicles is combined and one-phase method is performed The number of vehicles K is determined and feasible initial solution is generated Two vehicles are selected using selection method (Fig.8) A sequence of old solution is partially replaced to a new sequence Is it a feasible solution?