Advances in Continuous Approximation
Sina Ansari
Mehmet Basdere
Francisco JaraMoroni
12 / 05 / 2013
Literature Review of Selected Papers
from 1996 to 2013.
Main Classification
Facility Location Related Studies
Routing Related Studies
Other Studies
Classical Facility Location Problems
Reliability Related Problems
○ Verter and Dasci (2001),
A continuous model for productiondistribution system design.
• Aims to find the locations of the facilities that minimize the total fixed facility opening costs, facility operating costs and transportation costs of PDS.
•
Novelty:
The distance metric is assumed to be varying over the region of interest, K(x,y).
○ Dasci and Laporte (2005),
A continuous model for multistore competitive location.
• Aims to model the location strategies in a tworetail environment (leader and follower company). The decision variables are the locations of the stores for both firms. The formulation is based on CA and analytically tractable. Insights are obtained for different strategies of leader and follower firms.
•
Novelty:
Competitive facility location environment is considered. No disruption risk.
○ Shen and Qi (2007),
Incorporating inventory and routing costs in strategic location models.

Not exactly a CA model.
Uses routing cost estimates of CA in strategic level location problem (original model in the study is a nonlinear integer programming model).
○ Murat et al. (2010),
A continuous analysis framework for the solution of location–allocation problems with dense demand
• Aims to find facility locations and allocations over a region with dense demand.
•
Novelty:
Allocation decisions are given before the location decisions. In simple terms, the boundaries of the regions are determined first and the algorithm moves the boundaries as it searches for a better solution.
 A more specific version is discussed in Murat et al. (2011) for a two facility environment.
○ Carlsson and Jia (2013),
Continuous facility location with backbone network costs.
• Aims to locate facilities to minimize the cost including the costs from backbone network.
•
Novelty:
Backbone network (although a very special type) is considered.
○ Li and Ouyang (2010),
A continuum approximation approach to reliable facility location design under correlated probabilistic disruptions.
• Aims to find facility locations in an environment with disruptions.
•
Novelty:
Considers correlated disruptions.
○ Cui et al. (2010),
Reliable facility location design under the risk of disruptions.
• Aims to locate facilities under random disruptions.
•
Novelty:
Region dependent disruption probabilities are considered.
○ Li and Ouyang (2012),
Reliable traffic sensor deployment under probabilistic disruptions and generalized surveillance effectiveness measures.
• Aims to locate sensors to maximize surveillance in traffic flow with a limited budget.
•
Novelty:
Region dependent failure probabilities are considered in a for 1D problem.
○ Wang and Ouyang (2012),
A continuum approximation approach to competitive facility
location design under facility disruption risks.
• Aims to locate facilities in a competitive environment. (Nash and Stackelberg settings are considered.)
•
Novelty:
Deals with disruption in a competitive environment.
○ Lim et al. (2013),
Facility location decisions with random disruptions and imperfect estimation.
• Aims to locate reliable and unreliable facilities in a randomly disrupted environment.
•
Novelty:
Region dependent disruption probabilities are considered.
Classical Routing Problems
○ Francis and Smilowitz (2006),
Modeling techniques for periodic vehicle routing problems.
• Aims to find an assignment of nodes to service schedules and a set of vehicle routes for each day of the planning period that.
[onetomany]
•
Novelty:
CA is applied to a new type of problem.
○ Smilowitz and Daganzo (2007),
Continuum Approximation Techniques for the Design of Integrated Package Distribution Systems.
•
Aims to find density of terminals, item and vehicle routings for a distribution system.
[manytomany]
•
Novelty:
Compares fully integrated networks and nonintegrated networks for expedited and deferred deliveries. Considers repositioning costs of vehicles.
○ Ouyang (2007),
Design of vehicle routing zones for largescale distribution systems
• Aims to
automatically discretize vehicle routing zones (VRZ) from continuum approximation guidelines
•
Novelty:
utilizing a combination of spatial partitioning techniques to systematically obtain optimum zone designs
○ Agatz et al. (2012),
Time slot management in attended home delivery.
• Aims to determine time slots for different service regions. Tradeoff is the cost effectiveness vs. service level.
[onetomany]
•
Novelty:
development of a fully automated approach capable of producing highquality time slot schedules much faster than the current manual process; Comparison of performance of CA and MIP model
○ Huang et al. (2013),
A continuous approximation approach for assessment routing in disaster relief
•Aims to address timesensitivity in the assessment routing problem(ARP) which routes teams to different communities to assess damage and relief needs following a disaster
•
Novelty
: illustrate the use of continuous approximation in developing routing schedules for humanitarian relief/introduce a hybrid strategy that improves upon the solutions from the continuous approximation model by exploring alternate route sequencing with a tabu search
Integrated Problems
○ Suzuki and Drezner (1997),
On the airline hub model: The continuous model.
• Aims to find the hub locations in rectangular areas where the airports are evenly spread.
[manytomany]
•
Novelty:
One of the first papers that use CA in hub location problem.
○ Saberi and Mahmassani (2013),
Modeling the airline hub location and optimal market problems with continuous approximation techniques.
• Aims to find optimal hub selection of a new company and optimal market selection for an existing company with known hubs.
[manytoone & onetomany]
•
Novelty:
A more realistic framework for hub location problem. Location decisions are integrated with routing decisions.
Other studies
○ Miyagava (2009),
Optimal hierarchical system of a grid road network.
 Not a direct application of classical CA. CA is used to calculate the travel distance to develop a better road network. The study provides insights about ratio of different type of roads.
○ Shu and Karimi (2009),
Efficient heuristics for inventory placement in acyclic networks.
 Tries to determine safety stocks in acyclic networks. CA is used to solve a concave minimization problem approximately.
○ Wang et al. (2012),
Reliability modeling in spatially distributed logistic systems.
 CA is used to calculate reliability on different levels in distributed logistic systems.
○ Daganzo et al. (2012),
The potential of parsimonious models for understanding large scale transportation systems and answering big picture questions.
 A review paper not exactly on CA but on parsimonious models such as CA models with low number of variables.
Current Trends, Gaps and Future of CA
Trends
○ Citations Network
Gaps
The Gaps Identified by Langevin et al. (1996)
• Lack of studies in manytomany distribution systems with transshipments and peddling.
 Smilowitz and Daganzo (2007).
• Few reported applications.
 Francis and Smilowitz (2006), Agatz er al. (2012), Saberi and Mahmassani (2013) ...
• Different costs (other than transportation and inventory) must be considered.
 Smilowitz and Daganzo (2007) [vehicle relocation cost], Carlsson and Jia (2013) [backbone network cost].
• Time windows and duration constraints seems lacking.

Agatz er al. (2012).
Future of CA
Current Gaps and Future of CA
• CA can be used as an effective tool to improve the exact solution methods.
 Most of the studies ignore exact formulations claiming that they are hardtosolve problems and focus on CA.
 Efficient integrations can make exact problems solvable within a reasonable amount of time.
 CA can be used more frequently during the exact algorithms (not only as a good start).
 Huang et al. (2013) a sample paper tried to investigate an hybrid method
• CA can be used as a tactical or even operational problems.
 Most of the studies use it as a strategical level planner.
 CA has a good potential in providing quick, easytoapply and 'nearoptimal' solutions in dynamic environments.
• Authors must focus on the applicability aspect of CA when discussing the solution quality.
 Optimal solutions are the best ones in terms of quality; however, easiness and applicability decrease the unexpected costs caused by users.
• Other application domains must be considered to encourage the use of CA.
 Wireless sensor networks can be a very good example for CA application. Generally, WSN are large networks and sensor locations are not determined exactly.
• Metric for comparison of CA Modeling and Discrete modeling
....
Summary
Methodological
○ Du et al. (1999),
Centroidal Voronoi tessellations: Applications and algorithms.
 A review paper that describes CVT and some potential applications (such as image processing and resource allocation).
 The resource allocation problem that they pick is the mail box placement problem for a postal service and the aim is to minimize the travel cost of users to the mailbox.
○ Galvao et al. (2007),
A multiplicativelyweighted Voronoi diagram approach to logistics districting.
• Aims to partition the existing customer network while balancing the load factors.
•
Novelty:
Weighted Voronoi diagrams are used and shown to be performing well on the regions where the load factors change from one subregion to another.
○ Ouyang and Daganzo (2006),
Discretization and validation of the continuum approximation scheme for terminal system design.
• Aims to discretize the facility location solutions provided by CA.
•
Novelty:
Improvement on the only known discretization scheme (Centroidal Voronoi Tessellation) and prevents undesirable shape generation.
Facility Location Related Papers
Routing Related Papers
Present Remotely
Send the link below via email or IM
CopyPresent to your audience
Start remote presentation Invited audience members will follow you as you navigate and present
 People invited to a presentation do not need a Prezi account
 This link expires 10 minutes after you close the presentation
 A maximum of 30 users can follow your presentation
 Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
CA Recent Literature
IEMS 489
by
Tweet