一类公路网络检查站寻址的问题

Location Problem of Survey Station in Road Network

考虑了一类在公路网络中设立检查站的最优选址的问题 ,在给定的G(V ,A)中 ,V是点集 ,A是弧集 ,(vsi,vti) (i=1,2 ,… ,)是给定的r个O D(origin destination)对 ,已知vsi到vti的车辆通过相应路线的概率 ,不超过给定检查站数目L的条件下 ,如何合理地在边上确定检查站 ,使得通过检查所截的路线总数的期望值最大 .建立了此问题的整数线性模型 ,给出基本算法思想 。

A location problem of survey station in road network which can be stated as: given a road network G(V,A) where V is the set of node and A is the set of link in the network, (v si,v ti)(i=1,2,...,r) are the given r O-D pairs. Suppose that the possibilities of each route the automobiles, go from v si to v ti are given, how to choose the opimal location of a given number of survey stations so that the expected number of O-D pair checked is maximized. This problem first be formulated as mixed integer linear programming model, then a basic ideal calculation method is provided to solve it, finally a heuristic greedy algoritihm for approximate solutions is adopted.