Time-Constrained Routing Optimization Models And Algorithms Under Uncertain Travel Times

Routing optimization problems are classical problems in the research areas of operations research and management science.Typical routing optimization problems include shortest path problem,traveling salesman problem,vehicle routing problem,etc.In the application areas of,for instance,transportation and logistics,computer network,and communication,many real-world problems are essentially routing optimization problem.Hence,the related researches of routing optimization not only have significant academic values,but also have comprehensive application values.Along with the high-speed development of international economics and society,the paces of human being's lives get faster and faster,and the time becomes more and more valuable.Hence,in transportation and logistics systems delivering people,the behavior factors bring challenges in routing optimization researches.Under this background,researching time-constrained routing optimization problems becomes more and more important and urgent.Findings can help travelers arrive at the destinations timely,etc.In real world,travel times are uncertain.Ignoring the uncertainty in the planning phase may cause the so-called optimal route to violate the pre-specified time constraint in the implementation phase.For instance,uncertainty causes the itinerary's travel time to exceed the time budget,and the customers' delivery times to the airport to be earlier or later than the time windows,etc.But considering the uncertainty would further complicate the routing optimization problems,and thus bring modelling and solution challenges.This thesis focuses on routing optimization problems,aims at meeting the prescribed time constraints as much as possible,considers travel times' uncertainty,proposes a research framework,and apply it into a public-transport itinerary planning problem,a traveling salesman problem,and a problem of pickup and delivery of customers to the airport.The research content mainly include the following five:(1)A research framework for time-constrained routing optimization problems under uncertain travel times is proposed.This framework comprises four aspects:constructing feasible set of routes,describing uncertainty in travel times,choosing decision criterion,and designing efficient algorithms.Different options are provided for each aspect,and hence the framework is able to explain most previous related work,and to create new research opportunities.When the travel times' distribution is fully known,only some descriptive statistics are known,or only the bounds are known,the paradigms of stochastic programming,distributionally robust optimization,or robust optimization are adopted to model and solve the problems.Particularly,regarding the decision criterion for measuring"meeting the time constraints",since the classical "on-time arrival probability" criterion is computationally inefficient and is unaware of the lateness magnitude,this thesis proposes a new class of decision criteria,maximizing the risk-hedging index(conservatism coefficient in robust optimization,risk-averse parameter in utility function,variance's weight in Markowitz mean-variance function,etc.),while guaranteeing that the corresponding travel time under this risk-hedging index would satisfy the time constraints.This class of decision criteria,besides having salient managerial properties,can be optimized in computationally efficient ways.Hence,they can be applied in solving real-world large-scale problems.(2)For urban public-transport travelers,the research focuses on itinerary planning problem with time budget,adopting robust optimization to model and solve the problem,for the purpose of helping the travelers arrive at the destinations within the time budgets as much as possible.The vehicular travel times are characterized via an uncertainty set.The robust optimization model maximizes the volume of the uncertainty set while guaranteeing on-time arrival over the uncertainty set,i.e.,maximizes the number of uncertainty scenarios of on-time arrivals.Through the duality theory,an exact algorithm is proposed.If a traveler uses each transit line at most once,a label-setting algorithm and a Floyd-A*speeding-up algorithm is proposed to efficiently solve the problem over a constructed trip-based network.Through a comparative study against a stochastic programming model that maximizes the on-time arrival probability,the itinerary travel time obtained via robust optimization is found to have lower expected tardiness and lower standard deviation.A computational test over the Shenyang public transport network indicates that less than one second is required per itinerary query in average,which verifies the Floyd-A*algorithm's applicability in solving real-world large-scale problems.(3)The research focuses on the aforementioned itinerary planning problem with time budget,but considers the case where the travel times' distribution is known,and uses stochastic programming to model and solve the problem.The expected utility theory is adopted to characterize the risk-averse behavior of travelers.The model maximizes the level of risk aversion while guaranteeing on-time arrival of the corresponding itinerary's certainty equivalent of uncertain travel time,i.e.,maximizes the capability of hedging against uncertainty.The decision criterion is proved theoretically to account for both the lateness probability and the expected tardiness.Since the problem with fully correlated travel times is NP-hard,the research focuses on two polynomially solvable cases with independent travel times and with correlated travel times within each transit line.The problem is decomposed into two stages,and thus solving the problem is equivalent to solving a sequence of itinerary planning problems without time budget.Through numerical studies,this method is found to perform "between" the model that maximizes the on-time arrival probability and that minimizes the expected tardiness.When implementing the algorithm over Shenyang public transport network,less than one second is required for an itinerary query in average,which verifies that the algorithm can be applied in real-world large-scale problems.(4)The research focuses on the classical traveling salesman problem with time windows.A so-called essential riskiness index is proposed as the decision criterion to evaluate the risk of arriving after the time windows at customer nodes.This index has the salient properties of convexity and others;it considers both the lateness probability and the expected tardiness.In the situations where the travel times' distribution is fully known and only their means and covariance are known,stochastic programming with sample average approximation and distributionally robust optimization are adopted to model and solve the problem,respectively.To accelerate the computation,a Benders decomposition combined with cutting plane algorithm is developed.Computation experiments indicate that,when the number of samples is small,the model with the essential riskiness index amazingly outperforms the model that maximizes the on-time arrival probability in terms of the on-time arrival probability itself.When the number is large,the model that maximizes the on-time arrival probability cannot be solved within acceptable computation time,but the Benders decomposition method can effectively involve a large number of samples.(5)The research focuses on the problem of pickup and delivery of customers to the airport.Aiming at minimizing the transportation costs,the problem determine the vehicle routing and scheduling arrangement to pick up and deliver customers who bought flight tickets to the airport,such that their delivery times are within the time windows with a probability guarantee.Chance-constrained stochastic programming and distributionally robust optimization models are established.For cases where the arc travel times follow independent normal distributions or only the means and covariance are known,analytical counterpart of chance constraints are derived;for the general distribution case,the sample average approximation(SAA)technique is used to address it.A two-phase algorithm is designed,which is exact except the SAA part.The first phase is to generate feasible routes and the second stage is to determine a set of optimal vehicle routes via set partitioning.A bisection approach is proposed to solve the problem that,under a cost budget constraint,maximizes the probability of delivery times within the time windows.Through a comparative study against an existing deterministic model,it is verified that the proposed models would reduce the lateness probability and expected tardiness.