3.3智能流程构造及优化
满足用户需求的Web服务发现后，下面的工作就是如何构造智能流程。为了构造智能流程，首先定义行程图。
定义5行程图(schedulegraph)：行程图G = (V, E)是带权无向图，其中V是顶点的集合，E是边的集合。图中的顶点V表示智能流程指定的出发地点、终止地点和每一个旅游景区的所在地。每个顶点有代价属性，代价属性表示在这一顶点所需要的费用代价（包括食宿的费用和旅游景区的费用）或者时间代价（即在这个顶点停留的时间）；图中的边集合中的每一个元素Di-Dj表示从顶点Di到顶点Dj之间有直达的交通工具，每一条边按照需求被赋予了一定的权值。
在智能流程构造时，游客关心的主要因素是时间和费用，因为行程图中每个顶点的费用代价和时间代价已经确定，影响智能流程的总时间和总费用的另一个重要因素就是顶点之间的交通因素。因此，形成智能流程时，从交通工具耗费的时间和费用2个方面进行考虑，为此将行程图细化，形成了费用行程图和时间行程图。
定义6费用行程图(costschedule graph)：在行程图定义时，如果边上的权值是地点Di到地点Dj之间交通工具消耗的最小费用，称其为费用行程图。
定义7时间行程图(timeschedule graph)：在行程图定义时，如果边上的权值是地点Di到地点Dj之间交通工具消耗的最小时间，称其为时间行程图。
借助行程图，将智能流程的构造问题转变为货郎问题。
根据费用行程图和时间行程图，分别形成交通费用最少的智能流程和交通耗时最少的智能流程，供游客进行选择。
行程图满足三角不等式，即对于图中的边所代表的城市之间的交通费用或者交通耗时满足： "vÎV：TrafficCost(vi,vk)<=TrafficCost(vi, vj) + TrafficCost(vj, vk)，或者"vÎV：TrafficTime(vi,vk)<=TrafficTime(vi, vj) + TrafficTime(vj, vk) 其中，TrafficCost(vi,vj)表示顶点vi和vj之间的交通费用，TrafficTime(vi,vj)表示顶点vi和 vj之间的交通耗时。
在货郎问题MM近似算法[15]的基础上，智能流程构造算法描述如下：
SmartflowConstructionAlgorithm
Input:TravelScheduleGraph = (V, E), start (startÎV), cost
Output:SmartFlow
T←KruskalMST(G)
//TistheMiniSpanTree of G
foreveryv∈T
ifthedegreeof v is odd then V’ ← V’ ∪ v
M←MinimumMatching(V’)
//Mistheminimum matching of V’
G’←T∪ M; //G’ is Euler graph
smartflow←smartflow∪ start
foreveryv∈G’
{
if v ∈ smartflow then
nextv
else
smartflow←smartflow∪ v
}
cost’←åthe cost of vertex in smartflow+ å the cost of edge in smartflow
ifcost’<=cost then
returnsmartflow
else
return‘no smartflow can be generated’
endif
在上述算法中，KruskalMST是计算行程图的最小生成树的算法，是多项式算法;MinimumMatching算法是计算最小生成树中基数顶点的最小对集的算法，也是多项式算法。因此，智能流程构造算法是多项式的。
4智能流程构造实例
根据对于旅游行业的调查[16]和参考旅游权威机构[17]制定的规范，建立了“平台”，包括SfDF、用户需求获取引擎、Web服务发现引擎和智能流程构造器。
在SfDF中，本体是最重要的语义基础，是其他描述组件的基础。将本体分为五类：地理本体、日期时间本体、交通本体、食宿本体和旅游景区本体。
以景区本体为例，除了所在地，景区还有很多其他的属性需要描述，这些属性能够帮助游客从多个角度观察景区，方便游客选择景区。比如：按照旅游资源，旅游景区可以分为五类，包括自然类旅游景区、人文类旅游景区、复合类旅游景区、主题公园类旅游景区和社会类旅游景区、其中自然类旅游景区又可以分为山地型自然旅游景区、森林类自然旅游景区、水景型自然旅游景区、洞穴型自然旅游景区和综合性自然旅游景区、按照景区的主导功能，旅游景区可以分为四类，包括观光类旅游景区、度假类旅游景区、科考类旅游景区和游乐类旅游景区；按照旅游景区的质量，旅游景区可以分为五类，包括1A级、2A级、3A级、4A级和5A级。另外，旅游景区还需要描述是否正常开放和开放周期等。在SfDF中，上述知识均作为领域知识，在本体中进行描述。
智能流程描述框架部分实例如下，包括旅游景区、智能流程约束和智能流程目标。
ClassScenicSpot
hasName ofType name
hasLongitude ofType longitude
hasLatitude ofType latitude
hasAltitude ofType altitude
hasCategory ofType category
hasComfortDegree ofType string
hasExcitementDegree ofType string
……
axiom IsOpen
definedBy
?x [ isOpen hasValue boolean ]
axiomvalidOpenCycle
definedBy
?X < ?Y ß ?Y memberOf date and ?X memberOf date and (?X.monthOfYear < ?Y. monthOfYear and ?X.year = ?Y.year) or(?X.year < ?Y.year)
