Jiahai Wang,,Yuyan Sun,Zizhen Zhang,and Shangce Gao,

Abstract—The multitrip pickup and delivery problem with time windows and manpower planning (MTPDPTW-MP)determines a set of ambulance routes and finds staff assignment for a hospital. It involves different stakeholders with diverse interests and objectives. This study firstly introduces a multiobjective MTPDPTW-MP(MO-MTPDPTWMP) with three objectives to better describe the real-world scenario. A multiobjective iterated local search algorithm with adaptive neighborhood selection(MOILS-ANS) is proposed to solve the problem. MOILS-ANS can generate a diverse set of alternative solutions for decision makers to meet their requirements. To better explore the search space, problem-specific neighborhood structures and an adaptive neighborhood selection strategy are carefully designed in MOILS-ANS. Experimental results show that the proposed MOILS-ANS significantly outperforms the other two multiobjective algorithms. Besides, the nature of objective functions and the properties of the problem are analyzed. Finally, the proposed MOILS-ANS is compared with the previous single-objective algorithm and the benefits of multiobjective optimization are discussed.

I.Introduction

THE vehicle routing problem(VRP)can be described as the problem of designing an optimal set of routes such that all the customers’requirements and the operational constraints are satisfied.The VRP has direct applications to everyday business routines of distribution or service-providing companies.A broad range of possible extensions to the VRP formulation are covered in [1]–[5].Most research focuses on a widely used variant,called VRP with time windows(VRPTW).Thereafter,further extensions of the VRPTW,such as the pickup and delivery problem with time windows(PDPTW),the dial-a-ride problem(DARP)and the multitrip VRP with time windows(MTVRPTW), were proposed[6]–[8].Besides,some research considers integrating the manpower planning into VRP since the driving of vehicles and the provision of services require the participation of manpower[9].Recently,a more practical variant,called multitrip pickup and delivery problem with time windows and manpower planning(MTPDPTW-MP) was introduced in[9].Relationship between this problem and other VRP extensions mentioned above is shown in Fig.1.

Fig.1.Relationship between MO-MTPDPTWMP and various VRP extensions.The problem highlighted in bold is studied in this paper.

MTPDPTW-MP is a real-life healthcare problem originated from the application of Hong Kong public hospitals,China.Transportation services are provided to disabled or elderly patients between their residences and clinics.The ambulance routes satisfying a series of constraints should be designed and the staff assignment is also required[10],[11].MTPDPTWMP is an NP-hard problem of high complexity,as it is a combination of two well-known NP-hard problems(i.e.,PDPTW and the staff scheduling problem).Usually,metaheuristic search techniques[12]are used to solve this kind of problems.In[9],an iterated local search(ILS)metaheuristic using a variable neighborhood descent(VND)procedure in the local search phase,called ILS-VND, was proposed to deal with MTPDPTW-MP.[9]considered MTPDPTW-MP as a single-objective problem.It optimized the weighted sum of unserved requests, total traveling cost,and the workload deviation.A fixed weight vector was used,where the number of unserved requests was set as the most important objective.Only one final solution is returned to decision makers as ILS-VND optiizes multiple objectives in a single-objective manner.

In practice,MTPDPTW-MP must consider the conflicting interests of different stakeholders(i.e.,the customers,hospital,and staff). According to[5],if we consider only one or two stakeholders in VRP variants, we may arrive at a local optimal solution because only one or two objectives are optimized in this situation.The interests of all stakeholders should be addressed in tandem[13].Due to the problem structures of MTPDPTW-MP,the improvement of one objective may lead to the deterioration of other objectives.Therefore,MTPDPTW-MP is essentially a multiobjective optimization problem(MOP).Solving it in a single-objective manner requires extensive domain knowledge to determine the relative importance of different objectives.The simple combination of three objectives into a single one,as in[9],fails to provide decision makers with a comprehensive understanding of the relationship between objectives.It is necessary to present decision makers with a set of representative Pareto optimal solutions,instead of a unique optimum for MTPDPTW-MP.The advantage is that it can provide considerable flexibility in terms of aposterioriselection of a single preferred solution that best suits the current requirements of decision makers[13],[14].

This study defines amultiobjective MTPDPTW-MP(MOMTPDPTWMP) with three objectives considering all stakeholders(e.g., the customers,hospital,and staff)to better reflect the real-world situation.The three objectives to be minimized include the number of unserved requests,the total traveling cost,and the workload deviation.The first one is customer-oriented:customers’requests should be served as many as possible.The second one is hospital-oriented, which can help to save money for the hospital.The third one is stafforiented:the daily workloads for different staff members should not have large variances.Then,an algorithm called multiobjective iterated local search algorithm with adaptive neighborhood selection(MOILS-ANS)is developed to solve the problem.In the proposed MOILS-ANS,seven problemspecific neighborhood structures are adaptively selected in the local search process based on their performances.

The contributions of this study are as follows:1)A multiobjective MTPDPTW-MP with three objectives considering the interests of all stakeholders is introduced.A multiobjective iterated local search algorithm with adaptive neighborhood selection(MOILS-ANS)is proposed to solve it.The proposed MOILS-ANS significantly outperforms the other two multiobjective algorithms.2)The nature of objective functions of MO-MTPDPTWMP is analyzed and important properties of MO-MTPDPTWMP are revealed.3)The proposed MOILS-ANS is compared with the previous single-objective algorithm and the benefits of multiobjective optimization are summarized.

The remainder of this paper is organized as follows.In Section II,problem formulation and related work are introduced.Thereafter,Section III provides a detailed description of the proposed MOILS-ANS.Experimental results are shown and analyzed in Section IV.Conclusions are drawn in Section V.

A.Problem Formulation and Related Work

A. MO-MTPDPTWMP

MTPDPTW-MP is formulated as a multiobjective problem(MO-MTPDPTWMP),which enables us to achieve a set of diverse and competitive solutions by addressing different objectives in a multiobjective manner.MO-MTPDPTWMP is a routing problem derived from the application of Hong Kong public hospitals,China.In this problem, the hospital can be regarded as the depot and ambulances can be regarded as vehicles.Each vehicle starts from the depot to accomplish some requests and returns to the depot within the maximum traveling duration.The goal of the problem is to design and schedule a set of optimal routes satisfying various constraints.Besides,the assignment of staff to vehicles should also be determined.A simple example with 8 requests and 2 vehicles is provided in Fig.2(a),in which there are 4 trips in total.The

Fig.2.Solution and its representation.(a)A possible solution;(b)Representation. A simple example with 8 requests and 2 vehicles is provided here.The depot node is0.The pickup nodes are {1+,2+,3+,4+,5+,6+,7+,8+}and their corresponding delivery nodes are{1?,2?,3?,4?,5?,6?,7?,8?}.Request8 is rejected owing to constraints.Solid lines represent trips for vehicle 1 while dashed lines represent trips for vehicle 2.The trip start time and staff ID are shown for vehicle 1,trip 1.

III.The Proposed Algorithm for MO-MTPDPTWMP

TABLE I Statistics of Performance Comparisons Between MOILS-ANS and MOILS-R

TABLE II Statistics of Performance Comparisons Between MOILS-ANS and MOEA/D-ANS

TABLE IV Thez-values,Unadjusted Pr pp-values, Adjusted p-values for the Friedman Test Along With Holm’s Post-Hoc Procedure According to HV and IGD at 5% Significance Level

TABLE III Average Ranking of MOILS-ANS,MOILS-R,and MOEA/DANS by Friedman Test According to HV and IGD

Moreover,the obtainedpvalues are less than 0.05 and MOILS-ANS obtains much higherR+values thanR?values on the multiproblem Wilcoxon signed-rank test.It means that MOILS-ANS is significantly better than MOILS-R.

To visually demonstrate the performance of MOILS-ANS and its two competitor algorithms,the projections of nondominated solutions of MOILS-ANS,MOILS-R,and MOEA/D-ANS(in red, blue,and purple,respectively)on a selected instance20090125 atf1–f2andf1–f3over 20 runs are compared with the Pareto front(in green dots),as shown in Fig.3.In the selected 2D plane(subspace), regions that are not fully covered by some algorithms are highlighted and marked with orange circles.

Comparing MOILS-ANS with MOILS-R from Fig.3,we can easily find that some regions of the Pareto front are not fully covered or approximated by MOILS-R. As shown in Fig.3(a),the final solution set obtained by MOILS-ANS spreads along the whole Pareto front,and is wider than those obtained by MOILS-R,as shown in Fig.3(c).Comparing Figs.3(b)and 3(d),we can find that MOILS-ANS covers all the regions of the Pareto front well,while MOILS-R misses some regions.Therefore,MOILS-ANS obtains better HV and IGD values than MOILS-R.

To sum up,MOILS-ANS outperforms MOILS-R.The effectiveness of the ANS strategy is revealed from comparisons between MOILS-ANS and MOILS-R.

2)Comparisons Between MOILS-ANS and MOEA/D-ANS:As summarized in Table II,MOILS-ANS significantly outperforms MOEA/D-ANS on 48 and 46 instances in terms of HV and IGD,respectively.Results of the multiproblem Wilcoxon signed-rank test show that MOILS-ANS is significantly better than MOEA/D-ANS in terms of HV and IGD.

Comparing MOILS-ANS with MOEA/D-ANS from Fig.3,we can easily find that some regions of the Pareto front are not fully covered or approximated by MOEA/D-ANS.As shown in Fig.3(e),although the final solution set obtained by MOEA/D-ANS spreads along the whole Pareto front,the solution set is not denser and closer to the true Pareto front as that of MOILS-ANS,as shown in Fig.3(a).Moreover,comparisons between Figs.3(b)and 3(f)show that MOEA/DANS misses some regions of the Pareto front,marked with the orange circle in Fig.3(f).

Fig.3.Nondominated solutions obtained by all algorithms on instance 20090125 over 20 runs.(a)MOILS-ANS at f1? f2;(b)MOILS-ANS at f1? f3;(c)MOILS-R at f1? f2;(d)MOILS-R at f1? f3; (e)MOEA/D-ANS at f1? f2;(f)MOEA/D-ANS at f1? f3.

Both MOILS-ANS and MOEA/D-ANS maintain and update a solution set,and they all can be seen as global search algorithms[16].In MOILS-ANS,a solution in the current solution set is randomly selected for exploration and updating in each iteration,while,in MOEA/D-ANS,the whole population is explored and updated from generation to generation.The main characteristic of MOILS-ANS is that it extends the single-objective ILS framework [9]with perturbation scheme for escaping local minima [16].Experimental results above show that MOILS-ANS performs better than MOEA/D-ANS.This might be due to the following reasons.In MOEA/D-ANS,it is likely that a highquality solution will gradually fill the large portion of the population with its variants/copies because the neighborhood is defined based on uniformly distributed weight vectors.This may lead to a loss of diversity of the population in MOEA/DANS.In contrast,the perturbation mechanism of MOILSANS can help MOILS-ANS to escape local minima, which leads to better convergence of the obtained solution set.

3)Summary:Table III shows the average ranking of all algorithms by Friedman test on all instances.Table IV shows the test statistics and adjustedp-values for the Friedman test along with Holm’s post-hoc procedure.In terms of both HV and IGD,MOILS-ANS gets the first rank,followed by MOEA/D-ANS and MOILS-R.In conclusion,the proposed MOILS-ANS significantly outperforms the two competitor algorithms,MOILS-R and MOEA/D-ANS.

F. Nature of Objectives and Problems

Fig.4.Parallel coordinates visualizing the alternative solutions generated by MOILS-ANS and the best solutions reported by the previous single objective algorithm.In each figure,our three objective functions are represented as three parallel axes.Each solution(a 3-D vector)is drawn as a polyline with vertices on the parallel axes;the position of the vertex on the ith axis corresponds to thei th objective value of the solution.The black line is the best solution reported by the previous single-objective algorithm and the gray lines are its alternatives generated by MOILS-ANS.(a)Instance 20090118;(b)Instance 20090122;(c)Instance 20090211;(d)Instance 20090218.

Understanding the nature of the relationships between objectives can help develop efficient and tailored problemsolving techniques in amultiobjective optimization problem.Usually,important properties of objectives and relationships between them can be revealed from thePF.Therefore,this study uses the method proposed recently in[33]to visualize and analyze the nature of objectives through thePF.For each instance,the approximatePFmentioned in Section IV-C is used asPFsince the truePFis unknown.Four randomly selected instances(i.e.,20090118,20090122,20090211,and 20090218)from all instances of January and February are chosen as representatives for analysis.We follow the four analysis steps used in[33].The corresponding analysis results are shown in Figs.S1–S5 in the Appendix.Observations can be concluded as follows.

1)The pairwise correlation values in Fig.S1 and the scatter plots in Fig.S5 show that conflicting relationship exists betweenf1?f2for the four selected instances.Fig.S2 shows that all objectives have large ranges.These large ranges also indicate that the selected four instances have conflicting objectives.Although there are solutions with good values for a given objective,at least one other objective has a poor value.To summarize,all the instances provide interesting multiobjective challenges.The improvement of one objective may lead to the deterioration of the other objective.Therefore,it is not wise to combine them into a single one using a fixed weight vector.

2)Fig.S4(a)shows that almost all regions have solutions,representing a wide variety of options for decision makers.Besides,Fig.S4(b)shows that the frequency of instances is high in most regions,meaning that the fitness landscapes of instances are alike.That is, recurring features exist in the fitness landscapes of different instances.Using this characteristic,it may be wise to solve one instance of a given problem scenario using computationally expensive multiobjective algorithms to obtain a good approximation set and then using goal programming with efficient singleobjective algorithms to solve other instances of the same problem scenario[34].

G.Comparisons With Previous Single-Objective Algorithm

1)Comparison Results:A single-objective algorithm called ILS-VND was proposed in[9] to deal with single-objective MTPDPTW-MP.The best solutions generated by ILS-VND are collected for comparisons since the same instances are solved by both multiobjective algorithms and ILS-VND.For each instance,all nondominated solutions generated by a multiobjective algorithm over 20 runs are combined to form its nondominated solution set,which is used to compare with the best solution generated by ILS-VND.

Table S2 in Appendix summarizes GDS and GAS values of MOILS-ANS,MOILS-R,and MOEA/D-ANS with respect to best solutions of ILS-VND for each instance.Table S3 in Appendix summarizes the number of nondominated solutions generated by MOILS-ANS,MOILS-R,and MOEA/D-ANS for each instance.Key observations can be found as follows.

a)All GDS values are zero.The single-objective algorithm invests all computing resources to optimize three objectives with a fixed weight vector,and returns just one solution finally.In contrast, the proposed multiobjective algorithm must make a balance among three objectives and return a set of tradeoff solutions finally.Therefore,it is quite difficult for the proposed algorithm to dominate the solution generated by the single-objective algorithm for MO-MTPDPTWMP.In this regard,all GDS values are 0.It suggests that the proposed algorithm may still have room for further improvement in future.

b)For each instance,GAS values show that each algorithm can generate numerous alternative solutions with respect to the best solution.These alternative solutions can provide decision makers with a wide variety of options to best suit their specific requirements[13],[14].

c)The proposed MOILS-ANS obtains the best GAS values on most instances(32 instances,about 54.24%of all 59 instances).Besides,the average GAS value of MOILS-ANS is the best among all multiobjective algorithms.

To sum up,MOILS-ANS performs best, which is in line with our previous analysis based on HV and IGD.

2) Benefits of Multiobjective Optimization:To illustrate the benefits of multiobjective MTPDPTW-MP,alternative solutions generated by MOILS-ANS on four selected instances(i.e.,20090118,20090122,20090211,and 20090218)are visualized using parallel coordinates in Fig.4.Our three objective functions are represented as three vertical axes in parallel coordinates.Each solution(a 3-D vector)is drawn as a polyline with vertices on the parallel axes,and the position of the vertex on theith axis corresponds to theith objective value of the solution.The black line is the best solution reported by the previous single-objective algorithm ILS-VND and the gray lines are its alternatives generated by MOILS-ANS.Observations can be found as follows.

a)For each instance,MOILS-ANS generates numerous alternatives with respect to the best solution.These alternatives can help decision makers to better understand the situation of the problem and provide them with more flexibility to select a solution that best matches their requirements.If all objectives are simply combined into a single one like ILS-VND, many alternatives will be lost during the search process.

b)Best solutions reported by ILS-VND always have good performances onf1.They are obviously customer-oriented solutions.The observation is reasonable becausef1is set as the most important objective in the single-objective algorithm ILS-VND.

c)Because of the inter-dependency among different objectives,a solution with the best performance on one objective has to compromise some other objectives.Therefore,“extreme”solutions with the best value for one objective may not be acceptable to decision makers.For example,customer-oriented solutions(black lines in Fig.4)provided by ILS-VND are the best in terms off1but poor in terms off2,f3.The interests of the hospital and the staff are ignored in these customer-oriented solutions.In such a situation,“middle ground” solutions that optimize all the objectives in the best possible way may be better choices[13].Formulating MTPDPTW-MP as a multiobjective problem can satisfy this purpose.It is evident from Fig.4 that we can choose a solution among its alternatives that performs a little worse onf1, but performs much better on bothf2,f3than the best solutions.

V.Conclusions

This study formulates MTPDPTW-MP as a multiobjective optimization problem to better meet the requirements of different stakeholders in real-world scenarios.To solve MOMTPDPTWMP,a multiobjective algorithm MOILS-ANS is proposed.Problem-specific neighborhood structures and an adaptive neighborhood selection strategy are designed to better explore the search space.Experimental results show that MOILS-ANS is significantly better than the other two multiobjective algorithms.The nondominated solutions obtained by all multiobjective algorithms for MOMTPDPTWMP are mined.The nature of objective functions and important properties of the problem are revealed.Moreover, by comparing solutions generated by MOILS-ANS with the best solutions generated by the previous singleobjective algorithm, the benefits of multiobjective optimization are summarized.The mining and analysis make a step towardexplainablemultiobjective optimization.

In the future,this study can be extended from several aspects.Firstly, the proposed algorithm requires a great deal of time when dealing with large scale instances.Therefore,the proposed algorithm can be speeded up through modern computing architectures,such as computer cluster and GPU,as in[35].It also can be extended to solve other multiobjective routing and scheduling problems[1].Secondly,the crossover operator is not adopted in the proposed algorithm and MOEA/D-ANS is in consistent with the existing multiobjective algorithms[2],[36]–[41].Previous experience[38]showed that the crossover of solutions in a highly constrained problem always produces infeasible solutions.Feasibility checking is too sophisticated for MOMTPDPTWMP.This means that a good crossover operator or repairing heuristics need to be designed,and thus the application of crossover-based algorithms to MOMTPDPTWMP is a possible research direction.Finally, the properties of MO-MTPDPTWMP can be further studied from nondominated solutions generated by the proposed algorithms.Making full use of problem-specific knowledge can improve the search ability of multiobjective algorithms.Selection of proper hyperparameters of the algorithms using the method in [42],[43]is also our future work.

Appendix

Fig.S1.Pairwise correlation values(y-axis)for each pair of objectives(xaxis)for four selected instances.The results for each instance are shown in different colors and linestyles.It shows the global pairwise relationships using the Kendall correlation method.Conflicting relationship(value< –0.5)exists between f1? f2, which indicates that the problem instances provide interesting multiobjective challenges.

TABLE SI Comparative Results (Mean and STD) Of HV and IGD on 59 Instances

TABLE SI (continued)Comparative Results (Mean and STD) Of HV and IGD on 59 Instances

TABLE SII Comparison of Multiobjective Algorithms with Previous Single-Objective Algorithm

TABLE SII (continued)Comparison of Multiobjective Algorithms with Previous Single-Objective Algorithm

TABLE SII (continued)Comparison of Multiobjective Algorithms with Previous Single-Objective Algorithm

TABLESIII Number of Nondominated Solutions Generated by MOILS-ANS,MOILS-R,and MOEA/D-ANS for Each Instance

TABLE SIII (continued)Number of Nondominated Solutions Generated by MOILS-ANS,MOILS-R,and MOEA/D-ANS for Each Instance

Fig.S2.Results for the objective ranges analysis for four selected instances.(a)Instance 20090118;(b)Instance 20090122;(c)Instance 20090211;(d)Instance 20090218.The y-axis presents the minimum,maximum,and average value of each objective as a percentage of the overall maximum value found for the respective objective.Longer lines indicate larger ranges.A ll objectives have large ranges(over 80%).It indicates that the selected four instances have conflicting objectives.Although there are solutions with good values for a given objective,at least one other objective has a poor value.More details can be found in [33].