属性权重信息不完全的双边匹配多目标决策模型的研究(pdf 6页).pdf

1 属性权重信息不完全的双边匹配多目标决策模型的 研究 属性权重信息不完全的双边匹配多目标决策模型的 研究 1 蒋忠中 1 盛莹2 樊治平1 袁媛3 1 东北大学工商管理学院 辽宁沈阳 110004 2 东北大学理学院 辽宁沈阳 110004 3 东北大学信息科学与工程学院 辽宁沈阳 110004 E mail zzjiang 摘摘 要要 以 C2C 电子商务为实际背景 研究了在商品属性权重信息不完全的情况下买卖双 方的双边匹配问题 首先给出了 C2C 电子商务中商品属性权重信息不完全的双边匹配问题 的数学描述 然后在此基础上 以最大化匹配度和交易额为目标 建立了双边匹配多目标决 策模型 并依据该模型是一类多目标混合 0 1 整数二次规划模型的特点 设计了模型的求解 方法 最后通过一个仿真实例的计算 说明了模型及求解方法的有效性和可行性 关键词关键词 双边匹配 C2C 电子商务 信息不完全 属性权重 多目标决策 0 引言引言 随着 Internet 技术的发展 传统的商务活动逐渐向 Internet 转移 网上的商务交易不断 增加 在线用户和企业的数量如爆炸式增长 这一方面促进了电子商务的蓬勃发展 另一方 面也带来了新的挑战 1 3 例如 在 C2C 电子商务中 企业虽然为买卖双方的用户提供了电 子交易平台 典型的有房产 汽车中介网站 但是这类交易平台目前大部分仅仅是一个替买 卖双方用户发布供需信息的场所 却并没有实现供需信息匹配的机制 因而 如何针对用户 的供需信息实现最优的双边匹配 提高交易效率和交易利润 已成为当前 C2C 电子商务企 业急需解决的关键问题 双边匹配早期的研究集中在婚姻匹配方面 4 5 近年来伴随电子商务的发展 少数国内 外学者已经开始关注电子商务领域的双边匹配研究 文献 6 考虑多个买家与多个卖家的情 况 以买方与卖方互为值域 以双方的属性是否得到满足为约束 将其转化为约束满足问题 进行求解 开发了求解器 并在房产中介网站中进行应用 文献 7 直接连接每一个可能进 行交易的买家与卖家 按属性满足程度对该连接进行评价 并按评价值大小进行匹配 文献 8 通过对用户输入参数的处理 估计出用户属性的权重及效用函数 计算匹配值 并介绍 了在餐饮业中服务于无线上网用户的应用 文献 9 建立了电子中介中多属性匹配的指派模 型并研究了模型的求解算法 然而 上述研究均未涉及到双边匹配时匹配属性权重信息可能是不完全的情况 另一方 面 对于双边匹配产生的利润价值亦缺乏充分考虑 为此 本文以 C2C 电子商务为实际背 景 以最大化匹配度和交易额为目标 建立了属性权重信息不完全的双边匹配多目标决策模 型 并探讨了模型的求解方法 1 问题的描述问题的描述 考虑在 C2C 电子商务中 双边匹配的对象即买卖双方的多个买家和多个卖家 各交易 一件同类多属性商品的情况 设有 m 个买家和 n 个卖家 分别以 bi和 sj表示 其中 i I i 1 本课题得到国家杰出青年科学基金项目 70525002 国家自然科学基金创新群体项目 70721001 国家 教育部高等学校博士点专项科研基金项目 20040145018 东北大学流程工业综合自动化教育部重点实验室 项目 JCLL 01 05 的资助 2 i 1 m j J j j 1 2 n 另设该类商品有l个属性 买家bi对商品属性k K k k 1 2 l 的要求 称之为约束 若为等号约束 称为硬约束 否则为软约束 而软约束又可分为三种 类型 1 效益型属性约束 如商品的品质 对买方而言该类属性越高 大 越好 2 成本型属性约束 如商品的价格 对买方而言该类属性越低 小 越好 3 区间型属性约束 即买方要求该类属性只要处于一个区间范围之内即可 设 k i c为买家 bi对商品效益型或成本型属性 k 的临界值 21 k i k i cc为买家 bi对商品区间 属性 k 的区间 卖家 sj商品的 k 属性值以 k j p表示 且买方对于商品各属性的权重 或偏好 信息不完全 本文要考虑的问题是 买方向 C2C 电子商务企业提交包括价格等各属性的要 求 即约束 及权重 而卖方则提交商品各属性值 包括卖价 匹配的条件是卖方的商品 属性值必须满足买方各约束 同时买方出价不低于卖方定价 匹配的目标是最大化匹配度和 交易额 为了便于建立解决该问题的数学模型 下面进一步给出买卖双方匹配度的概念 定义定义 1 称 sj匹配 bi 如果对于 硬约束 有 k i k j cp 2效益型属性约束 有 k i k j cp 成本型属性约束 有 k i k j cp 区间型约束 有 21 k i k i k j ccp 定义定义 2 设 1 0 k ij k i k Sp max k i k Sp min 其中 Si表示与 bi匹配的所有 sj集合 k i S表示 Si中属性 k 的值的集合 称 k ij 为 bi与 sj在属性 k 下的匹配度 若 k ij 满足下列条件 对于任何属性约束 如果 ij Ss 则0 k ij 否则 如果 ij Ss 满足 对于效益型 属性约束 有 kk j k ij pp max 对于成本型属性约束 有 k j kk ij ppmin 3对于硬约束和 区间型属性约束 有1 k ij 就买方而言 为了表示对属性匹配度的偏好 需给出商品属性的相对重要程度 即属性 权重 然而在现实生活中 买方可能给出属性权重信息不完全的情况 如各个属性权重的 大小关系或者大小的区间等 下面给出属性权重信息不完全的数学描述 记 w w1 w2 wl T W 为属性权重向量 其中 wk表示属性 k 的权重系数或重要程度 满足 Kk k w1和 wk 0 符号W 表示属性权重信息不完全的数学表达式的集合 具体地 可包括下列 5 种情况 10 11 121 kkk ww 211 kkk ww 4321 kkkk wwww k1 k2 k3 k4 111 kkk w 21121 kkkkk www 或 1211 kkkk ww 0 2 k w 这里 k1 k2 k3 k4 K 且对于 1 k 有 1 k 1 k 1 k 0 1 1 k 1 k 1 k 为正实 数 2 双边匹配多目标决策模型与求解方法双边匹配多目标决策模型与求解方法 基于上述问题的描述 建立如下属性权重信息不完全的双边匹配多目标决策模型 KkIiJj ij k ijk xwf 1 max 1 IiJj ij ji x pq f 2 max 11 2 2 3 s t 1 Ii ij x Jj 3 1 Jj ij x Ii 4 Wwk Kk 5 1 Kk k w 6 ij x0 或 1 Ii Jj 7 0 k w Kk 8 模型中 式 1 和 2 为目标函数 前者是从买卖双方角度考虑 最大化双边匹配的各属 性加权的匹配度 后者是从 C2C 电子商务企业角度考虑 最大化双边匹配的交易额 从而 实现企业自身的利润价值 通常情况下匹配的利润是按照交易额的比例收取 这里 1 i q表示 买家 i 对商品的出价 1 j p表示卖家 j 商品的价格属性值 匹配成功的成交价格取 1 i q和 1 j p之 间的中间值 式 3 和 4 为双边匹配限制 即至多允许双方一对一匹配 式 5 和 6 为信息不 完全情况下的属性权重约束 式 7 和 8 为模型的决策变量约束 其中 ij x为 0 1 整数变量 当1 ij x时表示买家 bi匹配卖家 sj 否则0 ij x 而 k w为非负的属性权重变量 不难看出 上述建立的多目标决策模型具有三个特征 1 第一个目标函数中含有二次 项 2 约束条件均是线性的 3 决策变量既有整数变量又有非整数变量 因而该模型是一 类多目标的混合 0 1 整数的二次规划模型 同时 模型中的两个目标函数具有不同的量纲 即一个是匹配度量 一个是交易额量 针对以上特点 本文设计了如下求解方法 首先 通过编程 本文采用 Visual B 编程语言 计算买卖双方商品的匹配度 k ij 从而为模型的下一步求解做准备 其次 求解各个单目标下的最优值 对于目标 f1 可利用 LINGO 软件求混合整数的二 次规划的方法求得其最优值 1 f 对于目标 f2 由于仅是 0 1 变量 ij x的函数 可以利用分支 定界算法或者 LINGO 软件直接求得该目标函数的最优值 2 f 最后 将模型的多目标转换为单目标并求解 多目标决策模型的求解方法有多种 12 14 其中一种有效的方法是将多目标转换成单目标进行求解 由于模型中两个目标函数的量纲不 一致 因而需要对其进行标准化处理 15 令标准化函数 1 1 1 f f F 2 2 2 f f F 显然 21 F F的 值域均为 0 1 同时考虑在通常情况下模型中的两个目标具有同样的重要性 进而构造新的 目标函数 21 FFf 替代模型中由 1 和 2 表示的两个目标函数 此时 便得到了相应的单 目标的混合 0 1 整数的二次规划模型 该单目标模型亦可利用 LINGO 软件求解 从而得到 最优的双边匹配对 3 仿真实例仿真实例 设某C2C电子商务企业运营的二手房产中介网站有如表1所示的买卖双方各20个的供需 4 信息 即双边匹配信息 二手房有6种属性 分别是价格 w1 面积 w2 建筑时间 w3 环境条件 w4 地点 w5 和楼层 w6 其中 地点为硬约束属性 面积和建筑时间为效 益型属性 价格和环境条件为成本型属性 而楼层为区间型属性 同时属性的权重满足 0 5w2 w1 0 6w3 w4 w3 w2 w1 w3 0 9w5 w2 0 7w6 通过计算得到最优的双边匹配对如表2所示 由表2可以看出 双边匹配产生了13对最优 匹配 产生的交易额是742 5万元 此时相应的属性权重系数分别为 w1 0 0830404 w2 0 1660808 w3 0 1384007 w4 0 2214411 w5 0 1537786 w6 0 2372583 为了对比分析 本文还进一步对于不考虑属性权重情况下的多目标决策模型 即略去原 模型 记为模型1 中的权重约束条件 5 6 8 及目标函数 1 的系数wk 记为模型2 采用 同样的方法求解 得到的最优双边匹配结果如表3所示 此时双边匹配产生了13对最优匹配 对 产生的交易额是742 5万元 不难看出 匹配对的数量和交易额与表2得到的结果相同 但是匹配对之间的对应关系发生了变化 表2中的b5 s15 b6 s5变成了表3中的b5 s5 b6 s15 由于模型1和2得到的匹配结果中买方 b1 b2 b4 b5 b6 b8 b10 b14 b15 b16 b17 b18 b20 和卖方 s1 s2 s3 s5 s6 s7 s9 s11 s12 s15 s17 s19 s20 没有改变 所以两种情况下计算得到的交易额一样 但是由于模型1考虑了属性权重信息不完全的因素 因而更能描述现实情况 产生的匹配结果更能满足买卖双方的供需要求 表1 买卖双方的二手房产供需信息 Table 1 The supply demand information list of buyers and sellers 买 方 价 格 万元 面 积 平米 建筑时间 年份 环境条件 级 地点 区 楼层 层 卖 方 价 格 万元 面 积 平米 建筑时间 年份 环境条件 级 地点 区 楼层 层 b1 45 90 1985 3 C 3 10 s1 451302000 3 C 3 b2 75 130 1995 4 C 2 9 s2 601102005 2 C 9 b3 60 70 1990 4 B 3 6 s3 45701995 1 A 6 b4 60 50 1995 5 B 3 8 s4 45502005 3 B 4 b5 90 70 2000 2 A 4 9 s5 30902000 1 A 7 b6 75 50 1985 4 A 6 10 s6 30701995 2 A 8 b7 90 110 1990 3 A 5 9 s7 301101990 3 C 7 b8 60 90 1985 5 C 4 9 s8 60501995 2 B 4 b9 75 110 2000 3 B 5 10 s9 601102000 1 A 7 b10 45 50 1985 4 A 3 6 s1030501995 3 B 5 b11 60 90 1990 5 B 4 9 s1160502005 1 B 5 b12 75 110 2000 3 B 3 6 s12601301995 3 C 8 b13 30 90 1985 5 B 4 7 s13 30802000 3 A 8 b14 75 70 1995 4 C 2 8 s1490702005 1 C 3 b15 45 70 1985 5 A 5 9 s1560702000 1 A 6 b16 60 50 1990 3 B 3 10 s16751301995 3 B 4 b17 75 70 1995 2 A 3 8 s1745902000 2 A 7 b18 60 110 1985 5 A 2 9 s18 30501995 3 B 5 b19 90 110 1995 3 C 2 8 s1945701995 4 B 8 b20 90 130 1990 4 C 4 10 s2060702000 1 C 3 5 表2 双边匹配最优匹配结果 Table 2 Optimal matching results of buyers and sellers 序号 1 2 3 4 5 6 7 匹配对 b1 s7 b2 s1 b4 s19 b5 s15 b6 s5 b8 s2 b10 s3 序号 8 9 10 11 12 13 匹配对 b14 s20 b15 s17 b16 s11 b17 s6 b18 s9 b20 s12 表3 不考虑属性权重情况下双边匹配最优匹配结果 Table 3 Optimal matching results of buyers and sellers without Information on Attribute Weights 序号 1 2 3 4 5 6 7 匹配对 b1 s7 b2 s1 b4 s19 b5 s5 b6 s15 b8 s2 b10 s3 序号 8 9 10 11 12 13 匹配对 b14 s20 b15 s17 b16 s11 b17 s6 b18 s9 b20 s12 4 结论结论 随着 Internet 技术的发展 传统的商务活动逐渐向 Internet 转移 电子商务正逐渐成为 经济增长的亮点和未来商务发展的趋势 因而电子商务领域的一系列问题已成为当前众多研 究者关注的焦点 本文针对 C2C 电子商务中在对买卖双方进行双边匹配时存在商品属性权 重信息不完全的问题 首先在给出 C2C 电子商务中商品属性权重信息不完全的双边匹配问 题的数学描述的基础上 以最大化匹配度和交易额为目标 建立了双边匹配多目标决策模型 并依据模型的特点设计了相应的求解方法 最后仿真实例表明了模型及求解方法的有效性和 可行性 因而本文的研究工作将对 C2C 电子商务企业提高交易效率和交易利润等方面具有 理论指导意义 参考文献参考文献 1 Collins J Bilot C Gini M Decision processes in agent based automated contracting J IEEE Transactions on Internet Computing 2001 5 2 61 71 2 Huhns M N Stephens L M Automating supply chains J IEEE Internet Computing 2001 5 4 90 93 3 王红兵 王铁成 谢俊元 智能买卖交互模型 J 计算机学报 2003 26 9 1190 1195 4 Irving R Leather P The complexity of counting stable marriages J SIAM Journal of Computing 1986 15 655 667 5 Mcvitie D G Wilson L B The Stable Marriage Problem J Communications of the ACM 1971 14 486 490 6 Jung J J Jo G S Brokerage between buyer and seller agents using constraint satisfaction problem models J Decision Support Systems 2000 28 293 304 7 Kwang M S Raymond C A brokering protocol for agent based e Commerce J IEEE Transactions on Systems Man and Cybernetics Part C 2000 30 4 474 484 8 Gaurav T Jim Y Pattie M Personalized location based brokering using an agent based intermediary architecture J Decision Support Systems 2002 34 127 137 9 张振华 电子中介中的交易匹配方法及其应用研究 D 沈阳 东北大学 2005 10 Ahn B S Park K S Han C H et al Multi attribute decision aid under incomplete information and hierarchical structure J European Journal of Operational Research 2000 125 431 439 11 于春海 樊治平 特征指标信息不完全的系统聚类方法 J 系统工程 2006 24 2 101 104 12 林锉云 董加礼 多目标优化的方法与理论 M 长春 吉林教育出版社 1992 55 167 13 Cohon J L Multiobjective Programming and Planning M New York Academic Press 1978 14 朱少英 徐渝 何正文 一种基于不同风险偏好投资多目标决策模型及解法 J 运筹与管理 2003 12 2 1 5 15 Zhou G G Min H Gen M A genetic algorithm approach to the bi criteria allocation of customers to warehouses J International Journal Production Economics 2003 86 1 35 45 6 Research on Multi objective Decision Model for Bipartite Matching with Incomplete Information on Attribute Weights Jiang Zhongzhong1 Sheng Ying2 Fan Zhiping1 Yuan yuan3 1 School of Business Administration Northeastern University Shenyang 110004 2 College of Sciences Northeastern University Shenyang 110004 3 School of Information Science and Engineering Northeastern University Shenyang 110