Click here to load reader

MAGISTERARBEIT - COnnecting REpositories · PDF file 2013-10-30 · 4.3.7 Restrictions ... MCNF Multicommodity Network Flow MIX Mixed Integer Programming NN Neural Networks PVRP Periodic

  • View
    0

  • Download
    0

Embed Size (px)

Text of MAGISTERARBEIT - COnnecting REpositories · PDF file 2013-10-30 · 4.3.7...

  • MAGISTERARBEIT

    Titel der Magisterarbeit

    „Delivery of Ready-Mixed Concrete in a

    Dynamic Environment“

    Verfasserin

    Sophie Bergthaler BA

    angestrebter akademischer Grad

    Magistra der Sozial- und Wirtschaftswissenschaften (Mag. rer. soc. oec.)

    Wien, 2010

    Studienkennzahl lt. Studienblatt: A 066 915

    Studienrichtung lt. Studienblatt: Magisterstudium Internationale Betriebswirtschaft

    Betreuer: Univ.-Doz. Dr. Karl Dörner

  • Page I

    Foreword First I would like to thank my professor Univ.-Doz. Dr. Karl Dörner who supported me

    in the search of an appropriate topic. Furthermore I would like to thank my professor

    Mag. Dipl. Ing. Dr. Verena Schmid for her continuous support and feedback. Without

    her I would have been lost.

    I would also like to thank my friends who always believed in me and supported me.

    In the end I would like to thank my family who gave me the possibility to study and

    supported me throughout my studies.

  • Page II

  • Page III

    Table of content

    FOREWORD ........................................................................................................................................ I

    TABLE OF CONTENT ..................................................................................................................... III

    TABLES ............................................................................................................................................... V

    TABLE OF FIGURES ......................................................................................................................... V

    TABLE OF ABBREVIATIONS ........................................................................................................ VI

    1 INTRODUCTION ...................................................................................................................... 1

    2 COMBINATORIAL PROBLEMS ............................................................................................. 2

    2.1 TRAVELING SALESMAN PROBLEM ............................................................................................. 2 2.2 VEHICLE ROUTING PROBLEM .................................................................................................... 4

    2.2.1 Capacitated Vehicle Routing Problem ............................................................................. 7 2.2.2 Distance-Constrained Vehicle Routing Problem .............................................................. 8 2.2.3 Vehicle Routing Problem with Time-Windows ................................................................. 8 2.2.4 Vehicle Routing Problem with Backhauls ........................................................................ 8 2.2.5 Vehicle Routing Problem with Pickup and Delivery ......................................................... 8

    3 SOLUTION METHODS ...........................................................................................................10

    3.1 CLASSICAL HEURISTICS ...........................................................................................................10 3.1.1 Saving algorithms ..........................................................................................................11 3.1.2 Sweep algorithm ............................................................................................................11 3.1.3 Petal algorithms.............................................................................................................11 3.1.4 Cluster-first, route-second algorithms ............................................................................12 3.1.5 Improvement heuristics ..................................................................................................12

    3.2 METAHEURISTICS ....................................................................................................................13 3.2.1 Attributes .......................................................................................................................13 3.2.2 Simulated Annealing ......................................................................................................14 3.2.3 Deterministic Annealing .................................................................................................14 3.2.4 Tabu Search ...................................................................................................................14 3.2.5 Genetic Algorithms ........................................................................................................14 3.2.6 Ant Systems ....................................................................................................................15 3.2.7 Neural Networks ............................................................................................................15

    3.3 VARIABLE NEIGHBORHOOD SEARCH ........................................................................................15

    4 READY-MIXED CONCRETE .................................................................................................18

    4.1 INTRODUCTION ........................................................................................................................18 4.2 HISTORICAL FACTS ..................................................................................................................18 4.3 NATURE OF CONCRETE ............................................................................................................19

    4.3.1 Perishable Material .......................................................................................................19 4.3.2 Customized Material ......................................................................................................20

  • Page IV

    4.3.3 Availability of Ingredients ..............................................................................................20 4.3.4 Continuous pouring........................................................................................................20 4.3.5 Sequential delivery .........................................................................................................20 4.3.6 Ordered and maximum amount ......................................................................................21 4.3.7 Restrictions ....................................................................................................................21

    4.4 CONCRETE PRODUCTION SYSTEM .............................................................................................21 4.4.1 Plant Capacity ...............................................................................................................21 4.4.2 Demand Fluctuation ......................................................................................................22 4.4.3 Placement Size ...............................................................................................................23 4.4.4 Orders ...........................................................................................................................23

    4.5 CONCRETE DELIVERY ..............................................................................................................24 4.5.1 Location ........................................................................................................................24 4.5.2 Delivery Cycle ...............................................................................................................24 4.5.3 Timing of Delivery .........................................................................................................25 4.5.4 Delivery Process ............................................................................................................25

    4.6 SPLIT DELIVERY MULTI DEPOT HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH TIME WINDOWS ........................................................................................................................................26 4.7 ORDERS ..................................................................................................................................27 4.8 PLANTS ...................................................................................................................................28 4.9 TRUCKS...................................................................................................................................28 4.10 MODEL ...............................................................................................................................29 4.11 METHODOLOGY BACKGROUND ............................................................................................30

    5 EXPERIMENTS ........................................................................................................................32

    5.1 STATIC EXPERIMENT................................................................................................................37 5.2 DYNAMIC EXPERIMENT............................................................................................................38 5.3 EX-POST EXPERIMENT .............................................................................................................39

    6 RESULTS ..................................................................................................................................41

    6.1 RUN TIME STUDY FOR THE STATIC EXPERIMENT ....................................................................

Search related