Limits...
Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem.

Schilde M, Doerner KF, Hartl RF - Eur J Oper Res (2014)

Bottom Line: This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP).The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning).The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.

View Article: PubMed Central - PubMed

Affiliation: Johannes Kepler University Linz, Institute of Production and Logistics Management, Altenberger Strasse 69, 4040 Linz, Austria ; University of Vienna, Department of Business Administration, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria.

ABSTRACT

In urban areas, logistic transportation operations often run into problems because travel speeds change, depending on the current traffic situation. If not accounted for, time-dependent and stochastic travel speeds frequently lead to missed time windows and thus poorer service. Especially in the case of passenger transportation, it often leads to excessive passenger ride times as well. Therefore, time-dependent and stochastic influences on travel speeds are relevant for finding feasible and reliable solutions. This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP). The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning). The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.

No MeSH data available.


Related in: MedlinePlus

Average (circles) and 95% confidence intervals (whiskers) of the gaps between the primary objective function values obtained by MPA and those obtained by MSA, depending on the percentage of dynamic requests grouped by instance size. Positive values indicate superior results obtained by the latter.
© Copyright Policy - CC BY
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4375618&req=5

f0035: Average (circles) and 95% confidence intervals (whiskers) of the gaps between the primary objective function values obtained by MPA and those obtained by MSA, depending on the percentage of dynamic requests grouped by instance size. Positive values indicate superior results obtained by the latter.

Mentions: Not all stochastic solution approaches appear equally suitable for the problem at hand. Whereas dynamic S-VNS is a promising concept, MSA does not obtain the same solution quality, even with the same underlying search procedure (see Fig. 5). Especially in larger problem settings with few dynamic requests, MSA cannot compete with the results obtained by MPA (see Fig. 7). The quality of the results obtained by the latter is very similar to that of the results obtained by dynamic VNS though. Nevertheless, MSA already offers a powerful approach for different problem settings (e.g., the vehicle routing problem with stochastic customers).


Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem.

Schilde M, Doerner KF, Hartl RF - Eur J Oper Res (2014)

Average (circles) and 95% confidence intervals (whiskers) of the gaps between the primary objective function values obtained by MPA and those obtained by MSA, depending on the percentage of dynamic requests grouped by instance size. Positive values indicate superior results obtained by the latter.
© Copyright Policy - CC BY
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4375618&req=5

f0035: Average (circles) and 95% confidence intervals (whiskers) of the gaps between the primary objective function values obtained by MPA and those obtained by MSA, depending on the percentage of dynamic requests grouped by instance size. Positive values indicate superior results obtained by the latter.
Mentions: Not all stochastic solution approaches appear equally suitable for the problem at hand. Whereas dynamic S-VNS is a promising concept, MSA does not obtain the same solution quality, even with the same underlying search procedure (see Fig. 5). Especially in larger problem settings with few dynamic requests, MSA cannot compete with the results obtained by MPA (see Fig. 7). The quality of the results obtained by the latter is very similar to that of the results obtained by dynamic VNS though. Nevertheless, MSA already offers a powerful approach for different problem settings (e.g., the vehicle routing problem with stochastic customers).

Bottom Line: This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP).The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning).The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.

View Article: PubMed Central - PubMed

Affiliation: Johannes Kepler University Linz, Institute of Production and Logistics Management, Altenberger Strasse 69, 4040 Linz, Austria ; University of Vienna, Department of Business Administration, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria.

ABSTRACT

In urban areas, logistic transportation operations often run into problems because travel speeds change, depending on the current traffic situation. If not accounted for, time-dependent and stochastic travel speeds frequently lead to missed time windows and thus poorer service. Especially in the case of passenger transportation, it often leads to excessive passenger ride times as well. Therefore, time-dependent and stochastic influences on travel speeds are relevant for finding feasible and reliable solutions. This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP). The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning). The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.

No MeSH data available.


Related in: MedlinePlus