Dynamic and Stochastic Planning Problems with Online Decision Making A Novel Class of Models Maria Lucia Arnoldina Gerarda Cremers
Publisher:
University of Groningen Groningen The Netherlands
Printed by:
PrintPartners Ipskamp
ISBN: 978-90-367-3756-2 c 2009 Maria L.A.G. Cremers
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system of any nature, or transmitted in any form or by any means, electronic, mechanical, now known or hereafter invented, including photocopying or recording, without prior written permission of the publisher.
Dynamic and Stochastic Planning Problems with Online Decision Making A Novel Class of Models
Proefschrift
ter verkrijging van het doctoraat in de Economie en Bedrijfskunde aan de Rijksuniversiteit Groningen op gezag van de Rector Magnificus, dr. F. Zwarts, in het openbaar te verdedigen op donderdag 9 april 2009 om 14.45 uur
door
Maria Lucia Arnoldina Gerarda Cremers geboren op 27 maart 1979 te Eindhoven
Promotores:
Prof. dr. M.H. van der Vlerk Prof. dr. W.K. Klein Haneveld
Beoordelingscommissie:
Prof. dr. F. Louveaux Prof. dr. G. Sierksma Prof. dr. L. Stougie
Voorwoord Een proefschrift schrijven? Promoveren? Dat nooit, was de heersende gedachte gedurende het grootste gedeelte van mijn studie. Je werkt hard, doet enorm je best en bent degene met de meeste kennis over je eigen onderwerp. Echter, bij geschreven stukken wordt door begeleiders veelvuldig de rode pen gehanteerd. En dat die rode pen dan soms groen, blauw of zwart is, maakt niet zo heel veel uit. Wellicht zult u zich nu verwonderd afvragen hoe het komt dat u mijn proefschrift in handen heeft. Het antwoord is simpel: onderzoek doen is leuk! Tot deze, voor mij ietwat verbijsterende, conclusie kwam ik tijdens het schrijven van mijn doctoraalscriptie. Al eerder had ik kennis gemaakt met diverse aspecten van de wetenschap, maar nog niet eerder was ik er zo door gegrepen. De oorzaak? Een onderwerp waar mijn hart sneller van gaat kloppen en een enorme enthousiaste en bedreven begeleider. Onder zijn bezielende leiding groeide de liefde voor het doen van onderzoek. Eerst dus tijdens mijn scriptie, maar later ook, zei het van wat meer afstand maar niet met minder enthousiasme, tijdens mijn promotietraject. De afgelopen vier en half jaar heb ik niet alleen veel geleerd over plannen onder onzekerheid en het bedrijven van wetenschap, maar ook over mezelf. De pieken en dalen die zo kenmerkend zijn voor een promotietraject zijn ook mij niet bespaard gebleven. Toch kijk ik met een tevreden gevoel terug en weet ik nog steeds heel zeker: onderzoek doen is leuk! Nu is het echter tijd voor een andere grote passie. Samen met Ruud ga ik vier en een halve maand door Zuidoost-Azi¨e trekken. En de toekomst? Die is nog onzeker, want zonder dat is het leven maar saai. Tot slot dank ik iedereen die bij heeft gedragen aan de totstandkoming van mijn proefschrift: voor het aanleren van vaardigheden en het geven van opbouwend commentaar, voor het lezen van het manuscript, voor het leveren van de broodnodige ontspanning en voor het verdragen van mijn talrijke buien. Vooral dat laatste was soms (erg) zwaar. Bedankt!
Marloes Cremers-van Schaik
Contents 1
2
Introduction
1
1.1
Routing and scheduling problems . . . . . . . . . . . . . . . . . . . .
2
1.2
Stochastic programming . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Online optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.4
Research objectives and approach . . . . . . . . . . . . . . . . . . . . .
6
1.5
Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.6
Included publications . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
A Two-stage Model for a Day-ahead Paratransit Planning Problem
13
2.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2
Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3
Two-stage recourse model . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.4
Solution method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.1
Clustering heuristic . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.4.2
Assignment heuristic . . . . . . . . . . . . . . . . . . . . . . . .
25
2.4.3
Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.5.1
Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.5.2
Parameters of the GA . . . . . . . . . . . . . . . . . . . . . . .
30
2.5.3
Late requests . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.5.4
Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.6
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.7
Comment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.5
3
A Dynamic Day-ahead Paratransit Planning Problem
37
3.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.2
Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
iv 3.3
Two-stage recourse model . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.4
Solution methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.4.1
Clustering heuristic second stage . . . . . . . . . . . . . . . . .
45
3.4.2
Assignment heuristic . . . . . . . . . . . . . . . . . . . . . . . .
47
3.4.3
Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.5.1
Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.5.2
Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . . .
51
3.5.3
Late requests . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
3.5.4
Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
3.5.5
DDaPP problem versus simplified problem . . . . . . . . . . .
55
3.6
Summary and conclusion . . . . . . . . . . . . . . . . . . . . . . . . .
58
3.7
Comment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
3.5
4 Fast Heuristics for a Dynamic Paratransit Problem
61
4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
4.2
Summary preceding paper . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.2.1
Problem description . . . . . . . . . . . . . . . . . . . . . . . .
63
4.2.2
Two-stage recourse model . . . . . . . . . . . . . . . . . . . . .
64
4.2.3
Heuristics of the discrete event simulation . . . . . . . . . . .
65
Alternatives for the heuristics . . . . . . . . . . . . . . . . . . . . . . .
66
4.3.1
Description of alternatives for the clustering heuristic . . . . .
67
4.3.2
Data of the small instances . . . . . . . . . . . . . . . . . . . .
70
4.3.3
Parameter setting of the heuristics . . . . . . . . . . . . . . . .
71
4.3.4
Choice of alternative . . . . . . . . . . . . . . . . . . . . . . . .
72
Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
4.4.1
Data of the realistic instances . . . . . . . . . . . . . . . . . . .
75
4.4.2
Parameter setting of the heuristics . . . . . . . . . . . . . . . .
77
4.4.3
Results realistic instances . . . . . . . . . . . . . . . . . . . . .
77
4.4.4
Results semi-realistic instances . . . . . . . . . . . . . . . . . .
80
Summary and conclusion . . . . . . . . . . . . . . . . . . . . . . . . .
83
4.3
4.4
4.5
5 A Dynamic Service Mechanic Problem for a Housing Corporation
85
5.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
5.2
Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
5.3
Two-stage recourse model . . . . . . . . . . . . . . . . . . . . . . . . .
89
5.3.1
90
First stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Contents 5.3.2
Second stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
5.4
Genetic algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
5.5
Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
5.5.1
Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
5.5.2
Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . . .
99
5.5.3
Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.5.4
Results for problem without overtime . . . . . . . . . . . . . . 104
5.6 6
v
Summary and conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 105
Summary and Discussion
107
6.1
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2
Discussion research objectives . . . . . . . . . . . . . . . . . . . . . . . 110
6.3
Directions for further research . . . . . . . . . . . . . . . . . . . . . . . 112
Bibliography
115
Samenvatting (Summary in Dutch)
121
