# Cross-Entropy Method in Application to the SIRC Model
## Appendix A Optimization by the Method of Cross-Entropy
### The Vehicle Routing Problem  
The classical vehicle-routing problem (VRP) is defined on a graph \(\mathbb{G}=(\mathbf{V},\mathcal{A})\), where \(\mathbf{V}=\{v_{0},v_{1},\ldots,v_{n}\}\) is a set of vertices and \(\mathcal{A}=\{(v_{i},v_{j}):i,j\in\{0,\ldots,n\}\), \(v_{i},v_{j}\in\mathbf{V}\}\) is the arc set. A matrix \(\mathbf{L}=(L_{ij})\) can be defined on \(\mathcal{A}\), where the coefficient \(L_{ij}\) defines the distance between the nodes \(v_{i}\) and \(v_{j}\) and is proportional to the cost of travelling by the corresponding arc. There can be one or more vehicles starting off from the depot \(v_{0}\) with a given capacity, visiting all or a subset of the vertices, and returning to the depot after having satisfied the demands at the vertices. The Stochastic Vehicle Routing Problem (SVRP) arises when elements of the vehicle routing problem are stochastic--the set of customers visited, the demands at the vertices, or the travel times. Let us consider that a certain type of a product is distributed from a plant to \(N\) customers, using a _single_ vehicle, having a fixed capacity \(Q\). The vehicle strives to visit all the customers periodically to supply the product and replenish their inventories. On a given periodical trip through the network, on visiting a customer, an amount equal to the demand of that customer is downloaded from the vehicle, which then moves to the next site. The demands of a given customer during each period are modeled as independent and identically distributed random variables with known distribution. A reasonable assumption is that all the customers' demands belong to a certain distribution (say normal) with varying parameters for different customers. The predominant approach for solving the SVRP class of problems is to use a \"here-and-now\" optimization technique, where the sequence of customers to be visited is decided in advance. On the given route, if the vehicle fails to meet the demands of a customer, there is a recourse action taken. The recourse action could be in the form of going back to the depot to replenish and fulfill the customers' demand continue with the remaining sequence of the customers to be visited or any other meaningful formulation. The problem then reduces to a stochastic optimization problem where the sequence with the minimum expected distance of travel (or equivalently, the minimum expected cost) has to be arrived at. The alternative is to use a re-optimization strategy whereupon failure at a node, the optimum route for the remaining nodes is recalculated. The degree of re-optimization varies. At one extreme is the use of a dynamic approach where one can re-optimize at any point, using the newly obtained data about customer demands, or to re-optimize after failure. Neuro Dynamic Programming has been used to implement techniques based on re-optimization (cf. e.g., [50]). The vehicle departs at constant capacity \(\mathsf{Q}\) and has no knowledge of the requirements it will encounter on the route, except for the probability distributions of individual orders. Hence, there is a positive probability that the vehicle runs out of the product along the route, in which case the remaining demands of that customer and the remaining customers further along the route are not satisfied (a failure route). Such failures are discouraged with penalties, which are functions of the recourse actions taken. Each customer in the set can have a unique penalty cost for not satisfying the demand. The cost function for a particular route traveled by the vehicle during a period is calculated as the sum of all the arcs visited and the penalties (if any) imposed. If the vehicle satisfies all the demandson that route, the cost of that route will simply be the sum of the arcs visited including the arc from the plant to the first customer visited, and the arc from the last customer visited back to the plant. Alternatively, if the vehicle fails to meet the demands of a particular customer, the vehicle heads back to the plant at that point, terminating the remaining route.