A tool that prepares data for an areal interpolation

http://www.mediafire.com/?1s6n2kc891yg4oa

(C) Copyright: Jong-Geun Kim. 2006-2011. All rights reserved.

This tool cannot be used for any commercial purposes without a written permission of the author. Contact the author (j g k i m 2 5 at gmail.com) for any questions.
=======================

This is a ArcGIS tool developed by model builder that prepares data for an areal interpolation. This tool requires two polygon feature classes (FC) and overlays the two. Originally base FC is assumed to be Traffic Analysis Zone (TAZ) while source FC being a census FC (tracts). Source FC must have a field representing population for each feature.

This tool transfers source FC's attributes to base FC while estimating the proportion of population (Pop_Portion) in the overlaid area. This Pop_portion value can be interpreted as the proportion of souce FC's contribution to the base FC. Implicit assumption is that each feature in the source FC has an even distribution of population, which is not necessarily the case with the featuers in the base FC.

Once Pop_portion fied is populated by this tool, next steps are 1) multiply an attribute field with the Pop_portion; 2) summarize the product by the case field uniquely assigned for base FC (e.g: TAZ_Name).

Know the rules of game and be willing to play better within the rules

Publish or perish.

<Stochastic traffic assignment with single-pass algorithm>

The steps of "double-pass" algorithm can be referred to page 288-292 of Sheffi (1984), but we cannot find more details there about the "single-pass" procedure which favor over the original ("double-pass") one.

 

YOSEF SHEFFI (1984) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Inc., Englewood Cliffs, New Jersey 07632

Dial RB. A Probabilistic Multipath Traffic Assignment Model Which Obviates Path Enumeration. Transportation Research 1971;5(2):83-111

Markov Decision Process

BKX (1995) of Transportation Science is about FILM based on probabilistic flows. Since its direct formulation is non-linear, they applied Markov decision process (MDP) to re-formulate the model as a mixed-integer programming.

MDP a discrete time stochastic process. Wiki (http://en.wikipedia.org/wiki/Markov_decision_process) explains it as follows:

At each time step, the process is in some state s, and the decision maker may choose any action as. The process responds at the next time step by randomly moving into a new state s', and giving the decision maker a corresponding reward R_a(s,s'). that is available in state

The probability that the process chooses s' as its new state is influenced by the chosen action. Specifically, it is given by the state transition function P_a(s,s'). Thus, the next state s' depends on the current state s and the decision maker's action a. But given s and a, it is conditionally independent of all previous states and actions; in other words, the state transitions of an MDP possess the Markov property.

Markov decision processes are an extension of Markov chains; the difference is the addition of actions (allowing choice) and rewards (giving motivation). Conversely, if only one action exists for each state and all rewards are zero, a Markov decision process reduces to a Markov chain.

 

This stochastic version of FILM, however, may not be able to consider deviation of consumers at least with current structure of formulation. Because it only looks at the turning probabilities at each node to its incident node and d

Deviation or exploration

I know I should focus on preparing my final defense and publishing my dissertation. But I am already looking for other things that might not be directly related to those tasks but rather out of my curiosity or (I hate to say this) instant interests. Whenever I encounter new concepts or ideas, I couldn't put the new things aside. They keep bothering me and tend to take the priority, which in may times turns out to be a bad practice. I should try harder to change my bad habit so that I can balance things I am juggling with and start something new only after more important tasks are done or almost finished.

Questions for the future

Column generation algorithm

So I realized that column generation algorithm is a useful approach in solving shortest path problem with resource constraints (SPPRC). Then the questions are;
1-1. How to generate the reduced cost paths for the sub-problem that will generate columns for the master problem.
1-2. A dynamic programming approach such as Dijkstra's SP algorithm is not feasible for SPPRC? even for generating paths in the sub-problem?
2.  When thinking of its application to maximum covering location problems (MCLP) or more specifically my problem (deviation-flow refueling location model: DFRLM),
- the master problem becomes a set covering with cardinality (p) constraint after MCLP was reformulated as a modified p-median problem and,
- the sub-problem may be solved by a Lagrangian relaxation method.  I wanted emphasize though that Lagrangian relaxation approach would be possible only if we already know all the 'candidate' paths.
- Good news is that the modified PMP could take any functional form for specifying the cost coefficients. This implies that the column generation approach can be easily applicable to the FILM with deviation case. Again if there are two types of weights in the network, then solving a SPPRC in advance as a pre-processing may be required.

- tentative algorithm
1. locate p facilities
2. Modify the network so that for each node in p, set node label: - vehicle range. This implies resource will be replenished at the nodes being evaluated.
3. SPPRC on the modified network.
//reduced cost paths....

How about solving master problem in the MCLP + column generation?

(review of the theoretic fundamental of column generation algorithm)
Reduced cost sigma(j) = c(j) - phi *A(j), where phi is the vector of optimal dual variables.
In the case of stock cutting problems, for a column x(j) >=0 to be eligible to enter the basis of a min problem, sigma(j) has to be negative. The sub-problem of finding the possible solution with the most negative reduced cost can be formulated as a special mixed integer programming problem, a knapsack problem.

However, in the case of PMP, to solve it by a Lagrangian relaxation, first it was relaxed using surrogates, which could be an arbitrarily number but here we made sure it is the same as the vector of optimal dual variables(phi).

Another set of questions branches out from here: relationship between Lagrangian relaxation and column generation (Dantzig-Wolfe decomposition). In fact, Huisman et al (2005) showed the two ways in which the two techniques can be combined efficiently. To be more specific, Lagrangian relaxation can be applied to the master problem to approximate the optimal values of the dual variables or it can be used on the original compact formulation of the problem to generate good columns.
In sum, this approach is based on the observation that when the Lagrangian relaxation is obtained by dualizing exactly those constraints that are the linking constraints in the Dantzig-Wolfe reformulation, the same sub-problem results. Consequently, the solutions generated by the Lagrangian sub-problems can also be added as new columns to the master problem.
This approach is applicable to FILM with deviation case with a stringent assumption of shortest distance path. In other word, it couldn't be applied when there are resource constraints such as vehicle range in traveling along paths. If FRLM or DFRLM are to be solved using a column generation algorithm more specifically in the framework of resource-constrained shortest path problem, additional modeling consideration may be required. Given that SPPRC associates an edge with a decision variable whereas (D)FRLM assigns a decision variable to a node, we would need to model the relationship between an edge and a node where a facility is located.

Vehicle routing problem with time window is related to my questions? At least the formulation that I saw had a constraint that ensures one vertex is preceding the other.

test

what would it look like?