Stochastic Vehicle Routing Problem with Restocking

In: Business and Management

Submitted By Shkodran
Words 5634
Pages 23
UNIVERSITY OF VIENNA
Faculty of Business, Economics and Statistics Department of Business Administration

040661 KFK PM/SCM/TL: Seminar B (E) WS /2014 Stochastic Vehicle Routing Problem with Restocking

Professor :
O.Univ.Prof.Dr. Richard Hartl Vienna,2014

Student:
Shkodran Ahmeti 0851254

Table of contents
Table of contents List of figures 1.Introduction 1.2. Problem Presentation 2. Stochastic Vehicle Routing Problem With Optimal Restocking 3. Single Vehicle Routing Problem 4. Multiple Vehicle Routing 4.1. Heuristic Algorithms 4.1.1. Route-First-Cluster-Next Heuristic Algorithm 4.1.2. Cluster-First- Route- Second Algorithm 4.1.3. Improving the Heuristic Solution 5. Computational Study and Results 5.1. Set – partitioning problem formulation 5.2.Test of Algorithms over Problem Sizes and Expected Route Length Limits 5.3. Comparison of the Algorithms over Demand Variations 5.4. Comparison with a Deterministic Method

6. Summary References

List of figures
Figure 1 A desired truck route with restocking action of returning to the depot when a stockout occurs or in anticipation of a stockout Figure 2 The two updating Strategies a and b Figure 3 Defined or particular route of a single vehicle Figure 4 Expected costs of going directly to the next node Figure 5 Expected costs of the restocking action Figure 6 Monotonicity of function fj(q) Figure 7 Choosing the unused vehicle Figure 8 Forming the clusters Figure 9 Routing through the clusters Figure 10 Cyclic transfer Figure 11 String cross Figure 12 String exchange Figure 13 String relocation

ABSTRACT
This paper presents a Stochastic Vehicle Routing Problem SVRP, where just the customer demand was unknown and other parameters were determined. In comparison with the deterministic, problems in stochastic vehicle routing are harder to be solved because the uncertainity. In place just to take a recourse…...

Similar Documents

Routing Approaches of Delay Tolerant Networks

...©2010 International Journal of Computer Applications (0975 - 8887) Volume 1 – No. 17 Routing Approaches in Delay Tolerant Networks: A Survey R. J. D'Souza National Institute of Technology Karnataka, Surathkal, India Johny Jose National Institute of Technology Karnataka, Surathkal, India ABSTRACT Delay Tolerant Networks (DTNs) have evolved from Mobile Ad Hoc Networks (MANET). It is a network, where contemporaneous connectivity among all nodes doesn’t exist. This leads to the problem of how to route a packet from one node to another, in such a network. This problem becomes more complex, when the node mobility also is considered. The researchers have attempted to address this issue for over a decade. They have found that communication is possible in such a challenged network. The design of routing protocol for such networks is an important issue. This work surveys the literature and classifies the various routing approaches. discontinuity in the network. There are also methods that have employed additional mobile nodes, to provide better message delivery. Researchers are even exploring how the social interaction of humans can be utilized for routing in a DTN. This survey has made an extensive study of the various routing strategies taken by the researchers in the past few years. We have classified them based on the type of knowledge used for routing. 2. FLOODING BASED APPROACHES Knowledge about the network helps in deciding the best next hop. It can happen that......

Words: 6818 - Pages: 28

Private Vehicle Ownership

...Singapore Private Vehicle Ownership and Transportation Planning in Malaysia Noresah Mohd Shariff + School of Distance Education Universiti Sains Malaysia, 11800 Penang Malaysia Abstract. This paper analyzes current trends in private vehicle ownership in Malaysia. For the past decades private vehicle ownership has increased tremendously in this country which is partly due to the economic growth, rapid urban development, population growth and inadequate public transport availability and services. In 2010, Malaysia has a population of 28.3 million, 17.4 million private vehicle automobiles and 11.7 million registered drivers. Traditionally, income has been hypothesized as a major determinant of private vehicle ownership. However, the spatial arrangement of urban fabric has becoming more important determinant of owning a vehicle. Other determinants such as government policy, auto vehicle financing, household characteristics and travel characteristics are also important. Therefore this paper is analyzing the spatial determinants of private vehicle ownership in Malaysia with a special reference to the Penang Island. Penang Island is located on the northeastern region of Malaysia and is an industrialized and a highly developed island. Penang Island has a population of 575,498 in 2000 and 740,200 in 2010, an increase of 29 percent for the last 10 years. In 2010 alone, there are 111,882 number of new registered vehicles in Penang Island. As private vehicle ownership is also......

Words: 2528 - Pages: 11

Advanced Routing

...Linux Advanced Routing & Traffic Control HOWTO Bert Hubert Netherlabs BV Gregory Maxwell Remco van Mook Martijn van Oosterhout Paul B Schroeder Jasper Spaans Revision History Revision 1.1 DocBook Edition 2002−07−22 A very hands−on approach to iproute2, traffic shaping and a bit of netfilter. Linux Advanced Routing & Traffic Control HOWTO Table of Contents Chapter 1. Dedication.........................................................................................................................................1 Chapter 2. Introduction ......................................................................................................................................2 2.1. Disclaimer & License.......................................................................................................................2 2.2. Prior knowledge................................................................................................................................2 2.3. What Linux can do for you...............................................................................................................3 2.4. Housekeeping notes..........................................................................................................................3 2.5. Access, CVS & submitting updates..................................................................................................3 2.6. Mailing list..............................................

Words: 28706 - Pages: 115

Stochastic Volatility

...Using a Monte Carlo Method with stochastic volatility (the Heston Model) Aarhus School of Business and Social Science 2011 2 Acknowledgements My gratitude and appreciation goes to my supervisor Peter Lø chte Jø rgensen, for his kind and insightful discussion and guide through my process of writing. I was always impressed by his wisdom, openness and patience whenever I wrote an email or came by to his office with some confusion and difficulty. Especially on access to the information on certain Danish structured products, I have gained great help and support from him. 3 Abstract My interest came after the reading of the thesis proposal on strucured products written by Henrik, as is pointed out and suggested at the last part of this proposal, one of the main limitations of this thesis may be the choice of model. This intrigues my curiosity on pricing Asian options under assumption of stochstic volatility. At first, after the general introduction of strucutred products, the Black Scholes Model and risk neutral pricing has been explained. The following comes the disadvanges of BS model and then moves to the stochastic volatility model, among which the Heston model is highlighted and elaborated. The next part of this thesis is an emricical studying of two structured products embbeded with Asian options in Danish market and follows with a conclusion. Key words: structured products, Asian options, Black-Scholes model, stochastic volatilty, Heston model,......

Words: 17332 - Pages: 70

Routing Protocol

...3.1 Types Of Routing Protocols 2 3.1.1 Static Routing 2 3.1.2 Distance Vector Protocols 3 3.1.3 Link-State Protocols 4 3.1.4 Advanced Distance Vector Protocol 5 3.1.5 Path Vector Protocols 5 4.0 Protocol Decision Criteria 5 5.0 OSPF 8 6.0 EIGRP 18 7.0 Analysis 21 8.0 Recommendation 22 9.0 References 23 9.1 URLs 23 9.1.1 OSPF 23 9.1.2 EIGRP 24 9.2 Books 24 9.2.1 OSPF 24 9.2.2 EIGRP 24 Executive Summary The network is based on the TCP/IP protocol, which permits the efficient routing of data packets based on their IP address. Cisco routers are used at various points in the network to control and forward the data. Alcatel OmniSwitch switch/routers are also used in the Site 2 facilities. At the current point a decision is being made by on whether to keep the existing Alcatel infrastructure in the Site 2 facility or migrate that equipment to similar Cisco equipment as exists in Site 1. The current Alcatel equipment is experiencing severe problems such as hardware failures, power supply failures, operating system memory leaks resulting in reboots. If the decision is made to upgrade the Alcatel switch/routers then an evaluation will need to be made on what the proper routing protocol should be running corporate wide will be needed. This would be an evaluation of suitability of Enhanced Interior Gateway Routing Protocol......

Words: 8531 - Pages: 35

Ccna Routing

...American International University–Bangladesh Continuing Education Center (CEC)  02 8816173 Ext 406  www.cec.aiub.edu CCNA Routing and Switching Course Outline CCENT Introduction to Networks Routing & Switching Essentials Scaling Networks Connecting Networks CCNA CCNA 1 – Introduction to Networks This course introduces the architecture, structure, functions, components, and models of the Internet and other computer networks. The principles and structure of IP addressing and the fundamentals of Ethernet concepts, media, and operations are introduced to provide a foundation for the curriculum. By the end of the course, students will be able to build simple LANs, perform basic configurations for routers and switches, and implement IP addressing schemes. Chapter 1 2 3 4 5 6 7 8 9 10 11 Topic Exploring the Network Configuring a Network Operating System Network Protocols and Communications Network Access Ethernet Network Layer Transport Layer IP Addressing Subnetting IP Networks Application Layer It’s a Network Students who complete Introduction to Networks will be able to perform the following functions:  Understand and describe the devices and services used to support communications in data networks and the Internet  Understand and describe the role of protocol layers in data networks  Understand and describe the importance of addressing and naming schemes at various layers of data networks in IPv4 and IPv6 environments  Design, calculate, and apply......

Words: 1022 - Pages: 5

Routing

...IT, Web Routing Name: Institution: Routing A router is a network device capable of passing data between two networks. The most basic reason for using a router is to connect a LAN to the internet (Lowe, 2013). A bridge on the other hand sits between two types of networks, for example between an Ethernet and wireless (Pomerleau, 2009) Routers can be helpful under the following circumstances. To begin with, routers are capable of connecting different network architectures such as Ethernet and Token Ring networks and so if it is expected that the LAN network in our case will need to use different network architectures in the future, then routers will be best choice. Second, a router is more efficient than a bridge because a router will process information that is specifically addressed to it where as a bridge processes all messages it receives. Therefore, a router would increase network data processing speed thus will end up with an efficiently working network when using a router than when using a bridge. Next, routers are advantageous in circumstances when an organization needs to communicate to the external environment and therefore routers are capable of connecting to a Wide Area Network (WAN) such as the internet (Ogletree 2004). The capacity to connect to the external environment enables the organization to be in contact to the government for information on taxation as well as connection to customers, suppliers and even competitors. Furthermore, routers are......

Words: 1275 - Pages: 6

Stochastic Calculus

...This text is a survey of the general theory of stochastic processes, with a view towards random times and enlargements of filtrations. The first five chapters present standard materials, which were developed by the French probability school and which are usually written in French. The material presented in the last three chapters is less standard and takes into account some recent developments. AMS 2000 subject classifications: Primary 05C38, 15A15; secondary 05A15, 15A18. Keywords and phrases: General theory of stochastic processes, Enlargements of filtrations, Random times, Submartingales, Stopping times, Honest times, Pseudo-stopping times. Received August 2005. Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Basic notions of the general theory . . . . . . . . . . . . . . . . . . . . 2.1 Stopping times . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Progressive, Optional and Predictable σ-fields . . . . . . . . . . . 2.3 Classification of stopping times . . . . . . . . . . . . . . . . . . . 2.4 D´but theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 3 Section theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Projection theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 The optional and predictable projections . . . . . . . . . . . . . . 4.2 Increasing processes and projections . . . . . . ...

Words: 7720 - Pages: 31

Logistic: School Bus Routing

...be over emphasised. One of such LA faced with this dilemma is Middleton Local Education Authority (LEA) which has been chosen for the purpose of this study. In order to address this problem, a statement of the problem is defined with reference to the presenting issues. Secondly, the aims and objectives of this study is stated in an attempt to resolve the presenting issues. Thirdly, key definition of terms is addressed with reference to the school bus problem. Fourthly, a critical review of the literature whilst putting into perspective the methodologies adopted in research. Furthermore, findings from different approaches using computer programs to address the school bus problem are highlighted. In addition, a critical analysis of the school bus problem is attempted whilst putting into perspective transportation management systems, public policy and compliance, appreciation of public transport design and sustainable transport systems. An understanding and knowledge of UK based transport systems is demonstrated with an application to the case study problem. Lastly, limitations are acknowledged, recommendations and conclusions are drawn. Within this, future challenges relating to the school bus problem with reference to transportation systems are also highlighted. 2.0 STATEMENT OF THE PROBLEM The area covered in this study is Middleton LEA, Birmingham in West Midland United Kingdom. The scope of this study is scheduling of the school bus service to meet the demands of......

Words: 3933 - Pages: 16

Optimization Problem

...Technology Vol:7 2013-06-25 Optimization Using Simulation of the Vehicle Routing Problem International Science Index Vol:7, No:6, 2013 waset.org/Publication/15351 Nayera E. El-Gharably, Khaled S. El-Kilany, and Aziz E. El-Sayed Keywords—Discrete event system simulation, optimization using simulation, vehicle routing problem. points or require a solution to be found quickly. Computational time on the fastest computers for optimization methods has been too long for many practical problems. Cognitive, heuristic, or combination heuristic-optimization solution procedures have been good alternatives [8]. The aim of this work is threefold; to present a new mathematical formulation of the VRP problem that uses fewer decision variables, to show how to model the TSP problem as a discrete event simulation model, and to employ the developed simulation model in finding the optimum/near optimum solution of the problem. This paper is organized as follows: in Section II, the basic concepts of VRP and the solution techniques found in literature will be briefly discussed. In Section III, proposed problem formulations will be presented followed by the simulation model development and optimization using simulation in sections IV and V. Finally, in section VI, the conclusions drawn from this work are presented. I. INTRODUCTION II. LITERATURE REVIEW HE vehicle routing problem (VRP) is one of the most intensively studied problems in operations research, and this is due to its structural......

Words: 4604 - Pages: 19

Stochastic Modeling of an Automated Guided Vehicle System with One Vehicle and a Closed-Loop Path

...IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 5, NO. 3, JULY 2008 Stochastic Modeling of an Automated Guided Vehicle System With One Vehicle and a Closed-Loop Path Aykut F. Kahraman, Abhijit Gosavi, Member, IEEE, and Karla J. Oty Abstract—The use of automated guided vehicles (AGVs) in material-handling processes of manufacturing facilities and warehouses is becoming increasingly common. A critical drawback of an AGV is its prohibitively high cost. Cost considerations dictate an economic design of AGV systems. This paper presents an analytical model that uses a Markov chain approximation approach to evaluate the performance of the system with respect to costs and the risk associated with it. This model also allows the analytic optimization of the capacity of an AGV in a closed-loop multimachine stochastic system. We present numerical results with the Markov chain model which indicate that our model produces results comparable to a simulation model, but does so in a fraction of the computational time needed by the latter. This advantage of the analytical model becomes more pronounced in the context of optimization of the AGV’s capacity which without an analytical approach would require numerous simulation runs at each point in the capacity space. Note to Practitioners—This paper presents a model for determining the optimal capacity of an automated guided vehicle (AGV) to be purchased by a manufacturer. This paper was motivated by work......

Words: 8654 - Pages: 35

Stochastic Calculus

...Steven E. Shreve Stochastic Calculus for Finance I Student’s Manual: Solutions to Selected Exercises December 14, 2004 Springer Berlin Heidelberg NewYork Hong Kong London Milan Paris Tokyo Preface This document contains solutions to half the exercises appearing in Stochastic Calculus for Finance I: The Binomial Asset Pricing Model, Springer, 2003. Steven E. Shreve December 2004 Pittsburgh, Pennsylvania USA Contents 1 The Binomial No-Arbitrage Pricing Model . . . . . . . . . . . . . . . . 1.7 Solutions to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 7 7 2 Probability Theory on Coin Toss Space . . . . . . . . . . . . . . . . . . . . 2.9 Solutions to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 State Prices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.7 Solutions to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 American Derivative Securities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.9 Solutions to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Random Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.8 Solutions to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6 Interest-Rate-Dependent Assets . . . . . . . . . . . . . . . . . . . . . . ....

Words: 12957 - Pages: 52

Vehicle

... Roll No: B-37 Noida INTRODUCTION The automotive industry in India is one of the largest automotive markets in the world. It was previously one of the fastest growing markets globally, but it is currently experiencing flat or negative growth rates. In 2009, India emerged as Asia's fourth largest exporter of passenger cars, behind Japan, South Korea, and Thailand, overtaking Thailand to become third in 2010. As of 2010, India was home to 40 million passenger vehicles. More than 3.7 million automotive vehicles were produced in India in 2010 (an increase of 33.9%), making India the second fastest growing automobile market in the world (after China). India's passenger car and commercial vehicle manufacturing industry recently overtook Brazil to become the sixth largest in the world, with an annual production of more than 3.9 million units in 2011. From 2011 to 2012, the industry grew 16-18%, selling around three million units. According to the Society of Indian Automobile Manufacturers, annual vehicle sales are projected to increase to 4 million by 2015, not 5 million as previously projected. In 2011, there were 3,695 factories producing automotive parts in all of India. The average firm made US$6 million in annual revenue with profits close to US$400 thousand. The majority of India's car manufacturing industry is evenly divided into three "clusters". Around Chennai is the southernmost and largest, with a 35% revenue share, accounting for 60% of the country's......

Words: 1343 - Pages: 6

Routing

...CALL ROUTING IN TELEPHONE NETWORKS INTRODUCTION ROUTING is a process of finding a path from a source to every destination in the network. A routing protocol sets up a routing table in routers and switch controllers. A node makes a local choice depending on global topology Telephone calls must be routed across a network of multiple exchanges, potentially owned by different telephone carriers. The exchanges are all connected using trunks. Each exchange has many "neighbours", some of which are also owned by the same telephone operator, and some of which are owned by different operators. When neighbouring exchanges are owned by different operators, they are known as interconnect points. This means that there is really only one virtual network in the world that enables any phone to call any other phone. This virtual network comprises many interconnected operators, each with their own exchange network. Every operator can then route calls directly to their own customers, or pass them on to another operator if the call is not for one of their customers. Call Routing When a call is received by an exchange, there are two treatments that may be applied: • Either the destination terminal is directly connected to that exchange, in which case the call is placed down that connection and the destination terminal rings. • Or the call must be placed to one of the neighboring exchanges through a connecting trunk for onward routing. Each exchange in the chain uses pre-computed......

Words: 820 - Pages: 4

Hybrid Vehicle

...hybrid vehicle Abstract The topic of this research paper is the impact of hybrid electric vehicles (HEVs) on the environment and society. The methodologies used to carry out research on this topic include collecting information on HEVs, their components, pollution caused by the manufacturing of their batteries, their economics, and their safety. The conclusions of the report are that HEVs adversely impact the environment and society. iii Table of Contents Abstract ......................................................................................................................................... ii Table of Contents ........................................................................................................................... iii Table of Figures ............................................................................................................................. vi Introduction ................................................................................................................................... 1 1. Definition of the Problem ........................................................................................................... 6 1.1 Fossil Fuels ............................................................................................................................ 6 1.2 Air Pollution .......................................................................................................................... 7......

Words: 12114 - Pages: 49