[go: up one dir, main page]

CN111507577A - 一种基于K-means聚类算法的众包任务分配方法 - Google Patents

一种基于K-means聚类算法的众包任务分配方法 Download PDF

Info

Publication number
CN111507577A
CN111507577A CN202010218967.2A CN202010218967A CN111507577A CN 111507577 A CN111507577 A CN 111507577A CN 202010218967 A CN202010218967 A CN 202010218967A CN 111507577 A CN111507577 A CN 111507577A
Authority
CN
China
Prior art keywords
cluster
clustering
analysis
points
method based
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN202010218967.2A
Other languages
English (en)
Inventor
周学权
张华�
初佃辉
胡鑫
涂志莹
张小东
孟凡超
李春山
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Harbin Institute of Technology Weihai
Original Assignee
Harbin Institute of Technology Weihai
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Harbin Institute of Technology Weihai filed Critical Harbin Institute of Technology Weihai
Priority to CN202010218967.2A priority Critical patent/CN111507577A/zh
Publication of CN111507577A publication Critical patent/CN111507577A/zh
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
    • G06Q10/06311—Scheduling, planning or task assignment for a person or group
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/29—Geographical information databases
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/906—Clustering; Classification
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
    • G06Q10/083—Shipping

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • Economics (AREA)
  • General Physics & Mathematics (AREA)
  • Strategic Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Development Economics (AREA)
  • Quality & Reliability (AREA)
  • General Business, Economics & Management (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Tourism & Hospitality (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Remote Sensing (AREA)
  • Educational Administration (AREA)
  • Game Theory and Decision Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明公开了一种基于K‑means聚类算法的众包任务分配方法，包括订单任务聚类分析和配送人员当前位置聚类分析。本发明的有益效果是能够快速高效的获得以全局路径最短为目标的近似最优解。

Description

一种基于K-means聚类算法的众包任务分配方法
技术领域
本发明属于物流技术领域，涉及一种基于K-means聚类算法的众包任务分配方法。
背景技术
随着互联网行业的快速发展，电子商务也由此进入了高速发展模式。近年，以天猫、京东为代表的电子商务平台，创造了巨大的交易额，2018年快递业务量突破500亿件。物流配送作为电子商务的基础属性也受到了前所未有的挑战，是各企业为提升平台水准，服务质量，必须攻克的领域。末端物流作为与用户体验最贴近的一环，配送的便利性，时效性，安全性都将成为用户评价一个电子商务平台的直接因素。传统的配送模式仍存在着时效性难以保证，交通压力大，配送人力物力短缺，处理突发事件能力弱等一系列问题。基于众包的概念，整合利用社会闲置配送资源是本文解决人力物力资源短缺的核心思想及途径。智能匹配模块采用K-means聚类算法对货物与骑手所在位置进行聚类分析，再通过遗传算法获得以全局路径最短为目标的近似最优解，其中路径信息通过调用百度地图的路径规划业务获取。顺风车配送模块充分利用了社会的闲置资源及顺路优势，如上下班的途中顺路进行配送，减轻了调度压力及交通压力。
发明内容
本发明的目的在于提供一种基于K-means聚类算法的众包任务分配方法，本发明的有益效果是能够快速高效的获得以全局路径最短为目标的近似最优解。
本发明所采用的技术方案是包括订单任务聚类分析和配送人员当前位置聚类分析。
进一步，1)订单任务聚类分析：服务器端为所有待匹配的订单任务进行聚类分析，首先查询数据库获得所有待匹配订单任务的接收地址，调用百度地图 API地址编码获得对应的经纬坐标，随机选取K个点作为初始聚类中心，遍历所有点得出与其欧几米德距离最小的积累中心，并加入该聚类，重新计算聚类中心，再次遍历点集判断所属聚类，直到各聚类中心坐标不改变，得到聚类结果；
2)配送人员当前定位聚类分析：服务器端获得配送人员当前定位，并调用百度地图API地址编码获得对应的经纬坐标，获得订单任务聚类分析结果，遍历聚类中心点集，计算欧几米德距离判断配送人员所属聚类，将该聚类信息写入匹配池数据表中；
3)服务器端后台打印输出该用户所在位置的经纬坐标，及与各聚类中心的距离最小值，最终得出所属聚类结果。
具体实施方式
下面结合具体实施方式对本发明进行详细说明。
K-means聚类算法的实现过程分以下四个步骤：
①初始化样本，从样本中随机选出K个点作为初始质心。
②计算各样本点到各质心的距离，选择离该样本点最近的质心并加入该质心所属的划分簇。
③重新计算各簇的质心点。
④判断各簇的质心点是否发生改变，改变则重复②③，若无改变则得到结果。
本发明将算法集成到服务器端，只需将原有的随机坐标点数据集替换为货物总包待接收地址的经纬坐标值。当目标用户发起新增货物总包请求时，调用一次 K-means算法，确定该新增订单包的所属聚类。配送人员发起任务匹配请求时，根据用户当前定位信息，调用百度地图地址编码API获得其所在位置的经纬坐标。基于经纬坐标和已有的订单聚类分析结果，为配送人员确定其所在聚类，配送人员将在该聚类下进行任务分配。
本发明基于K-means聚类算法的众包任务分配方法包括订单任务聚类分析和配送人员当前位置聚类分析；
1)订单任务聚类分析
服务器端为所有待匹配的订单任务进行聚类分析。首先查询数据库获得所有待匹配订单任务的接收地址，调用百度地图API地址编码获得对应的经纬坐标。随机选取K个点作为初始聚类中心，遍历所有点得出与其欧几米德距离最小的积累中心，并加入该聚类。重新计算聚类中心，再次遍历点集判断所属聚类，直到各聚类中心坐标不改变，得到聚类结果。
2)配送人员当前定位聚类分析
服务器端获得配送人员当前定位，并调用百度地图API地址编码获得对应的经纬坐标。获得订单任务聚类分析结果，遍历聚类中心点集，计算欧几米德距离判断配送人员所属聚类，将该聚类信息写入匹配池数据表中。
3)服务器端后台打印输出该用户所在位置的经纬坐标，及与各聚类中心的距离最小值，最终得出所属聚类结果。
以上所述仅是对本发明的较佳实施方式而已，并非对本发明作任何形式上的限制，凡是依据本发明的技术实质对以上实施方式所做的任何简单修改，等同变化与修饰，均属于本发明技术方案的范围内。

Claims (2)

1.一种基于K-means聚类算法的众包任务分配方法，其特征在于：包括订单任务聚类分析和配送人员当前位置聚类分析。
2.按照权利要求1所述一种基于K-means聚类算法的众包任务分配方法，其特征在于：所述1)订单任务聚类分析：服务器端为所有待匹配的订单任务进行聚类分析，首先查询数据库获得所有待匹配订单任务的接收地址，调用百度地图API地址编码获得对应的经纬坐标，随机选取K个点作为初始聚类中心，遍历所有点得出与其欧几米德距离最小的积累中心，并加入该聚类，重新计算聚类中心，再次遍历点集判断所属聚类，直到各聚类中心坐标不改变，得到聚类结果；
2)配送人员当前定位聚类分析：服务器端获得配送人员当前定位，并调用百度地图API地址编码获得对应的经纬坐标，获得订单任务聚类分析结果，遍历聚类中心点集，计算欧几米德距离判断配送人员所属聚类，将该聚类信息写入匹配池数据表中；
3)服务器端后台打印输出该用户所在位置的经纬坐标，及与各聚类中心的距离最小值，最终得出所属聚类结果。
CN202010218967.2A 2020-03-25 2020-03-25 一种基于K-means聚类算法的众包任务分配方法 Pending CN111507577A (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010218967.2A CN111507577A (zh) 2020-03-25 2020-03-25 一种基于K-means聚类算法的众包任务分配方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010218967.2A CN111507577A (zh) 2020-03-25 2020-03-25 一种基于K-means聚类算法的众包任务分配方法

Publications (1)

Publication Number Publication Date
CN111507577A true CN111507577A (zh) 2020-08-07

Family

ID=71875852

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010218967.2A Pending CN111507577A (zh) 2020-03-25 2020-03-25 一种基于K-means聚类算法的众包任务分配方法

Country Status (1)

Country Link
CN (1) CN111507577A (zh)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112884319A (zh) * 2021-02-10 2021-06-01 腾讯大地通途（北京）科技有限公司 一种任务分配方法、装置、计算机设备以及存储介质
CN113469611A (zh) * 2021-06-10 2021-10-01 哈尔滨工业大学 一种快递众包配送任务调度方法、系统及设备
CN113723673A (zh) * 2021-08-18 2021-11-30 郑州时空隧道信息技术有限公司 一种订单指派方法及系统

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109002960A (zh) * 2018-06-12 2018-12-14 广东工业大学 一种基于评分机制和路径规划的在线订单分发及配送方法
CN109685295A (zh) * 2017-10-18 2019-04-26 北京京东尚科信息技术有限公司 货物揽收调度方法及装置、存储介质、电子设备
CN109816132A (zh) * 2017-11-20 2019-05-28 北京京东尚科信息技术有限公司 信息生成方法和装置
CN110348678A (zh) * 2019-05-31 2019-10-18 口碑(上海)信息技术有限公司 配送资源的调度及针对菜品配送的资源调度方法及装置

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109685295A (zh) * 2017-10-18 2019-04-26 北京京东尚科信息技术有限公司 货物揽收调度方法及装置、存储介质、电子设备
CN109816132A (zh) * 2017-11-20 2019-05-28 北京京东尚科信息技术有限公司 信息生成方法和装置
CN109002960A (zh) * 2018-06-12 2018-12-14 广东工业大学 一种基于评分机制和路径规划的在线订单分发及配送方法
CN110348678A (zh) * 2019-05-31 2019-10-18 口碑(上海)信息技术有限公司 配送资源的调度及针对菜品配送的资源调度方法及装置

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112884319A (zh) * 2021-02-10 2021-06-01 腾讯大地通途（北京）科技有限公司 一种任务分配方法、装置、计算机设备以及存储介质
CN112884319B (zh) * 2021-02-10 2023-11-03 腾讯大地通途（北京）科技有限公司 一种任务分配方法、装置、计算机设备以及存储介质
CN113469611A (zh) * 2021-06-10 2021-10-01 哈尔滨工业大学 一种快递众包配送任务调度方法、系统及设备
CN113723673A (zh) * 2021-08-18 2021-11-30 郑州时空隧道信息技术有限公司 一种订单指派方法及系统

Similar Documents

Publication Publication Date Title
CN111507577A (zh) 一种基于K-means聚类算法的众包任务分配方法
CN110222893B (zh) 共享交通资源的投放地点推荐方法、装置与电子设备
CN104462263A (zh) 一种利用数据库索引搜索门店的方法
CN106779910B (zh) 配送订单分配方法和装置
KR101586815B1 (ko) 통신형 내비게이션을 이용한 카풀 서비스 제공방법 및 시스템
CN102175252B (zh) 分布式多级道路网的动态融合与联合路径规划方法
CN101739617A (zh) 基于pda的旅游智能行程导航系统
CN110737665B (zh) 一种数据处理方法及装置
CN107194608A (zh) 一种面向残疾人社区的众包标注任务分配策略
CN110400107B (zh) 一种闲散运输业务的智能敏捷发现系统
CN106447547A (zh) 一种智能旅游平台及运行方法
CN111652676A (zh) 上车点推荐的方法、装置、设备及存储介质
CN111881368A (zh) 一种确定推荐上车点的方法和系统
CN112989194A (zh) 一种车联网用户请求与服务偏好融合的推荐方法及系统
CN105897887A (zh) 基于云计算平台的遥感卫星大数据处理系统及方法
CN114286284B (zh) 一种商圈分级方法及装置
CN115796629A (zh) 传统村落活力量化评价方法及系统、电子设备、存储介质
CN111626554B (zh) 订单指派方法、装置、计算机设备及计算机可读存储介质
CN112001646A (zh) 一种物料调度方法、装置、存储介质及电子设备
CN107895392B (zh) 一种时间地图的绘制方法
CN111625604B (zh) 一种基于区块链的出行服务质量高可信评价系统与方法
CN113971190A (zh) 一种电子地图的渲染方法、装置、终端和计算机存储介质
CN117273592A (zh) 一种物流场景下的门店配送方法
CN117195010A (zh) 一种基于混合聚类算法进行物流中心选址的方法
CN106940189B (zh) 导航系统中的经典线路获取方法、装置

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
RJ01 Rejection of invention patent application after publication

Application publication date: 20200807

RJ01 Rejection of invention patent application after publication