Luận văn Tối ưu tìm đường hệ thống giao thông công cộng Hà Nội

// (distance and predecessor) about the shortest path // from the source to each vertex // Step 1: initialize graph for each vertex v in vertices do distance[v] := inf // Initialize the distance to all vertices to infinity predecessor[v] := null // And having a null predecessor 19 distance[source] := 0 // The distance from the source to itself is, of course, zero // Step 2: relax edges repeatedly for i from 1 to size(vertices)−1 do //just |V|−1 repetitions; i is never referenced for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then distance[v] := distance[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then error "Graph contains a negative-weight cycle" return distance[], predecessor[] Độ phức tạp của thuật toán Bellman Ford là O(n*m), trong đó n là số đỉnh và m là số cung của đồ thị. 2.1.3. Thuật toán Floyd-Warshall Trong khoa học máy tính, thuật toán Floyd-Warshall là một thuật toán cho việc tìm kiếm đường đi ngắn nhất trong một đồ thị có trọng với trọng số cạnh dương hay âm đều được. Một lần thực hiện thuật toán sẽ tìm ra độ dài (tổng trọng số) của các đường đi ngắn nhất giữa tất cả các cặp đỉnh. Mặc dù nó không trả về chi tiết của các đường dẫn, nhưng có thể xây dựng lại các đường dẫn với các sửa đổi đơn giản cho thuật toán. Thuật toán Floyd-Warshall là một ví dụ về lập trình động và được xuất bản dưới dạng hiện được công nhận bởi Robert Floyd vào năm 1962. Tuy nhiên, về cơ bản nó giống như các thuật toán được Bernard Roy xuất bản năm 1959 và cả bởi Stephen Warshall vào năm 1962 vì đã tìm thấy sự đóng cửa quá độ của đồ thị và có liên quan chặt chẽ với thuật toán của Kleene (xuất bản năm 1956) để chuyển đổi một máy tự động hữu hạn xác định thành biểu thức chính quy. Công thức hiện đại của thuật toán như ba vòng lặp lồng nhau được mô tả lần đầu tiên bởi Peter Ingerman, cũng vào năm 1962. 20 * Thuật toán: Thuật toán Floyd-Warshall so sánh tất cả các đường dẫn có thể thông qua biểu đồ giữa mỗi cặp đỉnh. Hãy xem xét một biểu đồ G với các đỉnh V đánh số từ 1 đến N. Xem xét thêm một chức năng shortestPath(i,j,k) trả về con đường ngắn nhất có thể từ i đến j chỉ sử dụng các đỉnh từ tập hợp {1,2,,k} như các điểm trung gian trên đường đi. Bây giờ, với chức năng này, mục tiêu là tìm ra con đường ngắn nhất từ mỗi i cho mỗi j sử dụng bất kỳ đỉnh trong {1,2,,N}[3]. Đối với mỗi cặp đỉnh này, shortestPath(i,j,k) có thể là một trong hai trường hợp. Một là một con đường không đi qua k (chỉ sử dụng các đỉnh trong tập hợp {1,,k-1}[4] hoặc hai là một con đường đi qua k (từ i đến k và sau đó từ k đến i, cả hai chỉ sử dụng các đỉnh trung gian trong {1,,k-1}) Chúng tôi biết rằng con đường tốt nhất từ i đến j chỉ sử dụng các đỉnh 1 xuyên qua k-1 được định nghĩa bởi shortestPath(i,j,k-1) và rõ ràng là nếu có một con đường tốt hơn từ i đến k đến j, sau đó độ dài của con đường này sẽ là sự kết hợp của con đường ngắn nhất từ i đến k (chỉ sử dụng các đỉnh trung gian trong {1,,k-1}) và con đường ngắn nhất từ k đến j (chỉ sử dụng các đỉnh trung gian trong {1,,k-1}). Nếu w(i,j) là trọng lượng của cạnh giữa các đỉnh i và j, chúng ta có thể định nghĩa shortestPath(i,j,k) theo công thức đệ quy sau : trường hợp cơ sở là shortestPath(i,j,0) = w(i,j) và trường hợp đệ quy là shortestPath(i,j,k) = min(shortestPath(i,j,k-1), shortestPath(i,k,k-1) + shortestPath(k,j,k-1)). Công thức này là trái tim của thuật toán Floyd-Warshall. Thuật toán hoạt động bằng máy tính đầu tiên shortestPath(i,j,k) cho tất cả (i,j) cặp cho k=1, sau đó k=2, và như thế. Quá trình này tiếp tục cho đến khi k = N và chúng tôi đã tìm ra con đường ngắn nhất cho tất cả (i,j) cặp sử dụng bất kỳ đỉnh trung gian. Mã giả cho phiên bản cơ bản này như sau: 21 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) for each vertex v do dist[v][v] ← 0 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if Độ phức tạp của thuật toán Floyd-Warshall là O(n3), trong đó n là số đỉnh của đồ thị 2.2. THUẬT TOÁN TÌM ĐƯỜNG TỐI ƯU GIAO THÔNG CÔNG CỘNG TRÊN THIẾT BỊ DI ĐỘNG 2.2.1. Đồ thị mô phỏng hệ thống giao thông công cộng Hà Nội Ta có hệ thống giao thông công cộng của Hà Nội gồm hơn 2500 điểm dừng, và 141 tuyến xe. Các tuyến xe chính là đường đi qua các điểm dừng. Để mô hình hóa hệ thống giao thông công cộng Hà Nội thành đồ thị thì chúng ta coi mỗi một điểm dừng là một điểm của đồ thị, đường đi của tuyến xe qua các điểm dừng là cạnh có hướng, thời gian di chuyển giữa các điểm dừng chính là trọng số của cạnh đó. Như vậy mô hình hóa hệ thống giao thông công cộng Hà Nội chúng ta có một đồ thị G là một có hướng, có trọng số, đa đồ thị và gồm: - Khoảng 2500 đỉnh. - Khoảng 5600 cạnh. 2.2.2. Giải thuật tìm đường Điện thoại thông minh có rất nhiều ưu điểm để trở thành một công cụ hỗ trợ tìm đường nhưng nó lại có những nhược điểm cố hữu như tốc độ sử lý chậm, thời lượng pin hạn chế, giá thành dung lượng mạng di động cao. Để khác phục những nhược điểm này thì độ phức tạp của giải thuật tìm đường cho hệ thông 22 giao thông công cộng phải đủ nhanh để có thể sử lý ngay trên thiết bị thông minh. Đối với đồ thị G, giải thuật tìm đường đi ngắn nhất thông dụng như Dijkstra chạy trên điện thoại thông minh thường mất từ 7 đến 15 giây. Bài toán tối ưu hệ thống giao thông công cộng Hà Nội được cụ thể như sau: Có hai điểm A và B thuộc đồ thị G. Yêu cầu tìm đường đi từ A đến B có thời gian sử lý ít nhất và tổng trọng số đường đi từ A và B là ít nhất. Để tối ưu được đường đi cho bài toán trên chúng ta nhận thấy: - Do đi bộ mất nhiều thời gian nên sẽ trong giải thuật sẽ giảm tối đa thời gian đi bộ. - Thời gian để chuyển từ tuyến xe này sang tuyến xe khác là khá lớn, đó chính là thời gian đi bộ sang điểm dừng mới, thời gian chờ xe. Do đó giải thuật sẽ cần tìm ra số tuyến ít nhất. Trong giải thuật này tôi xe cố định số tuyến tối đa là 02 tuyến. - Lấy điểm A làm tâm vẽ một hình tròng với bán kính Ra = Rđi bộ (bán kính đi bộ Rđi bộ). Trong hình tròn sẽ có Na điểm dừng xe, dễ nhận thấy rằng Ra sẽ tỷ lệ thuận với Na. Tương tự với điểm B sẽ có Rb và Nb. Bây giờ bài toán tìm đường đi bằng đường bộ và bằng hệ thống giao thông công cộng từ điểm A đến điểm B sẽ chính là bài toán tìm đường đi bằng hệ thống giao thông công cộng từ các điểm dừng thuộc Na đến các điểm dừng thuộc Nb. Do đó nếu số Na và Nb tỷ lệ thuận với thời gian chạy thuật toán. Vậy muốn thời gian chạy giải thuật nhỏ thì Na và Nb phải nhỏ, tức là Ra và Rb sẽ phải nhỏ nhất có thể. Trong giải thuật này của tôi sẽ tìm đường đi ở mức Ra và Rb là 500m, nếu chưa tìm đường đi tối ưu thì sẽ tằng Ra và Rb lên 1000m. 23 Hình 4 Xác định các điểm dừng tại điểm đến và điểm đi - Mỗi một tuyến xe đều có một hướng tương đối cố định (trừ các tuyến vòng tròn). Có Gi là góc được tảo bởi vecto Vi của tuyến xe Ti với đường thằng vecto AB. Nếu góc Gi càng nhỏ thì sắc xuất đường đi tối ưu từ điểm A tới B có tuyến Ti càng lớn. Hình 5 Xác định góc của một tuyến xe Giải thuật: Đặt Rđi bộ = 500 m 24 Duyệt tất cả điểm dừng Da thuộc Na đối với tất cả điểm dừng Db thuộc Nb xem có tuyến Ti nào đi qua Da và Db sao cho đi qua Da trước Db Nếu nhiều tuyến Ti thì chọn tuyến Ti có ít thời gian nhất Hình 6 Mô tả đường đi khi đi bằng một tuyến xe Nếu không có tuyến Ti thì Tìm tất cả tuyến xe đi qua ít nhất một điểm dừng thuộc Na gọi là tập hợp tuyến Ta, sắp xếp các tuyến Ta theo thứ tự tăng dần góc Gi Tìm tất cả tuyến xe đi qua ít nhất một điểm dừng thuộc Nb gọi là tập hợp tuyến Tb, sắp xếp các tuyến Tb theo thứ tự tăng dần góc Gi Lặp các các bước sau cho đến khi tìm được tuyến xe hoặc khi hết cả hai tập hợp Ta và Tb : Lần lượt lấy một tuyến xe Tai từ đầu của Ta, lấy tất cả điểm dừng đằng sau của tuyến Tai từ điểm dừng thuộc Na gọi là tập hợp điểm Dai, cho tất cả các điểm Dai vào Na Kiểm tra lần lượt các điểm Dai xem có điểm nào có khoảng cách tới tập hợp điểm Nb <= Rđi bộ. Nếu có thì xuất kết quả 25 Lần lượt lấy một tuyến xe Tbi từ đầu của Tb, lấy tất cả điểm dừng đằng trước của tuyến Tbi từ điểm dừng thuộc Nb gọi là tập hợp điểm Dbi, cho tất cả các điểm Dbi vào Nb Kiểm tra lần lượt các điểm Dbi xem có điểm nào có khoảng cách tới tập hợp điểm Na <= Rđi bộ. Nếu có thì xuất kết quả Hình 7 Mô tả cách tìm đường đi bằng hai tuyến xe Nếu vẫn tìm được đường đi thì đặt Rđi bộ = 1000m rồi lặp lại quá trình như trên. 2.2.3. Độ phức tạp của giải thuật Chúng ta đều biết là độ phức tạp của giải thuật tìm đường đi ngắn nhất của Dijkstra là O(n2 + m) (trong đó n là số đỉnh, m là số cạnh). Với giải thuật của tôi đề xuất ở mục 2.2.2 thì trong trường hợp xuất nhất, trường hợp tập hợp các truyến xe Ta và Tb đi qua tất các điểm dừng của thành phố Hà Nội mà không có tuyến Ta nào trùng với một tuyến Tb thì độ phức tạp là O(n2). Trên thực tế với Rđi bộ = 500m thì thường có khoảng 10 điểm dừng, mỗi điểm dừng trùng bình có khoảng 10 tuyến đi qua thì tốc độ của giải thuật là O(10*10*2) = O(200) Với Rđi bộ = 1000m thường có khoảng 20 điểm dừng, mỗi điểm dừng trùng bình có khoảng 10 tuyến đi qua thì tốc độ của giải thuật là O(20*10*2) = O(400) 26 Thực nghiệm chạy giải thuật trên một chiếc điện thoại tầm trung có cấu hình trung bình thì giải thuật chạy mất tầm từ 1,5s đến 2s CHƯƠNG 3. XÂY DỰNG ỨNG DỤNG TRÊN THIẾT BỊ DI ĐỘNG 3.1. PHÂN TÍCH THIẾT KẾ ỨNG DỰNG 3.1.1 Bản đặc tả chức năng ứng dụng: 3.1.1.1 Bản tống quát chức năng: Actor Use cases Pre Condition / Post Condition Người dùng Tìm kiếm đường đi: - Lấy địa chỉ của User hiện tại để fill vào ô nhập địa chỉ điểm xuất phát. - User nhập địa chỉ cần đến (có hệ thống gợi ý địa chỉ). - Nhận thấy 2 ô địa chỉ đến và đi đã được fill thì lập tức tìm đường đi thông qua Google Map Api. - Hiển thị đường đi vs cụ thể các đoạn đi bộ, lên xe buýt, xuống xe buýt User phải nhập địa chỉ của cả đích đến và điểm xuất phát. User phải cho phép ứng dụng truy cập vị trí (cấp quyền - grand permission) Người dùng Tìm kiếm tuyến xe, điểm dừng: - User nhập từ khóa liên quan đến tên tuyến xe, địa chỉ điểm dừng 3.1.1.2. Khả năng áp dụng: Giao diện ứng dụng gọn, chỉ được phép hiển thị những thông tin cần thiết (User Interface), bố cục hợp lý để user có thể tập trung trải nghiệm chức năng chính, không bị xao nhãng bởi các chi tiết không cần thiết (User Experience). 3.1.1.3 Khả năng ổn định: Hệ thống ứng dụng phải chạy 24/7, hạn chế các trường hợp crash app không cần thiết gây hao tốn dung lượng pin của thiết bị và hạn chế thực hiện các request bừa bãi để hạn chế dung lượng mạng của user. 27 3.1.1.4 Hiệu suất mong đợi: Ứng dụng phải trả về lộ trình trong vòng 2.5s - 3.5s (cấu hình của thiết bị). Mong đợi sự hỗ trợ mang tới cho người dùng: - Giúp người dùng tìm được lộ trình hợp lý nhất. - Giúp người dùng tìm kiếm được thông tin về tuyến xe và điểm dừng - Hỗ trợ cả tiếng việt có dấu và tiếng việt không dấu. - Tạo cảm giác thoải mái, thiện cảm cho người dùng đối với xe buýt. 3.1.2 Sơ đồ luồng hoạt động của ứng dụng: 3.1.2.1. Sơ đồ luồng tìm kiếm thông tin: - Người dùng vào màn hình chính với địa chỉ hiện tại đã sẵn là vị trí hiện tại của điện thoại. - Người dùng nhập thông tin liên quan đến địa chỉ hoặc thông tin tuyến xe cần tìm. - Trong quá trình nhập ứng dụng đưa ra gợi ý địa chỉ để người dùng tăng tốc việc tìm kiếm. - Sau khi người dùng chọn một trong các gới ý của app thì app hiển thị thông tin về các điểm dừng xung quanh vị trí người dùng tìm hoặc thông tin về tuyến xe. 3.1.2.2 Sơ đồ luồng tìm kiếm đường đi: - Người dùng chạm vào biểu tượng chỉ đường ở góc bên dưới bên trái vào giao diện chỉ đường. - Người dùng nhập địa chỉ cần đến hoặc cả địa chỉ xuất phát nếu cần thiết. 28 - Trong quá trình nhập ứng dụng đưa ra gợi ý địa chỉ để người dùng tăng tốc việc tìm kiếm. Nhận biết khi có cả 2 địa chỉ được fill thì bắt đầu request để tìm đường. - Sau khi giải thuật tìm kiếm lộ trình. App hiển thị đường đi cho người dùng biết cùng cụ thể các đường nên đi đi bộ hay xuống ở điểm nào. Hình 8 Sơ đồ luồng tìm lộ trình đi xe của ứng dụng 3.1.3 Database: Sử dụng SQLite là hệ thống cơ sở dữ liệu quan hệ nhỏ gọn, hoàn chỉnh, có thể cài đặt bên trong các trình ứng dụng di động như Android. SQLite có các ưu điểm sau: - Tin cậy: các hoạt động transaction nội trong cơ sở dữ liệu được thực hiện trọn vẹn, không gây lỗi khi xảy ra sự cố phần cứng - Tuân theo tiêu chuẩn SQL92 - Gần như không cần cài đặt cấu hình - Kích thước chương trình nhỏ chỉ không đầy 300 kB 29 - Thực hiện các thao tác hệ thống cơ sở dữ liệu khách/chủ khác đơn giản nhanh hơn - Không cần có thêm phần mềm phụ trợ - Phần mềm tự do với mã nguồn mở, được chú thích rõ ràng 3.3.1 Điểm dừng: Dữ liệu của các điểm dừng được lưu riêng biệt để tiện cho việc tra cứu vào từng điểm dừng. Cấu trúc sẽ bao gồm: - name: địa chỉ trên thực tế - lat: vĩ độ của điểm dừng - lon: kinh độ của điểm dừng - route_go: lưu các tuyến xe chiều đi - route_return: lưu các tuyến xe chiều về - first: lưu các tuyến có điểm bắt đầu là điểm dừng này - finish: lưu các tuyến có điểm kết thúc là điểm dừng này 30 Hình 9 Cơ sở dữ liệu của điểm dừng 3.3.2. Tuyến xe Dữ liệu của các tuyến xe được lưu riêng biệt, có các trường sau đây: - name: tên gọi của tuyến xe - code: mã của tuyến xe - direction: hướng của chiều đi của tuyến xe - cost: giá một lần sử dụng tuyến xe - tghd: thời gian hoạt động của tuyến xe - ts: tần xuất tuyến xe - dv: đơn vị vận hành tuyến xe - station_go: lưu các id của điểm dừng trên chiều đi - station_return: lưu các id của điểm dừng trên chiều về - time_avg_go: thời gian trung bình di chuyển của các điểm dừng chiều đi 31 - time_avg_return: thời gian trung bình di chuyển của các điểm dừng chiều về Hình 10 Cơ sở dữ liệu của các tuyến xe 3.1.4 Thiết kế giao diện: 3.1.4.1 Prototype: Mục tiêu chính của phần này là thiết kế ra giao diện đăng nhập sao cho hợp lý, thích hợp UX/UI, thoáng, tập trung vào các chức năng chính. Trang Home (phần hiển thị map) 32 Hình 11 Thiết kế trang chủ của ứng dụng 3.4.1.4 Trang nhập địa chỉ Hình 12 Thiết kế giao diện nhập điện chỉ đến và đi 33 3.1.4.2 Deploy: Sản phẩm màn Home Hiện khi có lộ trình 34 Màn hình chức năng tìm điển dừng xung quanh một điểm 3.2. XÂY DỰNG ỨNG DỤNG TRÊN NỀN TẢNG ANDROID 3.2.1. Nền tảng Android Hiện nay, có rất nhiều nền tảng di động nhưng hai nền tảng Android và IOS đang thống lĩnh gần như 100% thị phần trong đó Android chiến 86,2% thị phần và IOS chiến 12,9 % thị phần (số liệu thống kê năm 2018). Do đó để nhằm tới lượng người dùng lớn, tôi đã chọn xây dựng ứng dụng trên nền tảng Android. Android là một hệ điều hành di động dựa trên phiên bản sửa đổi của nhân Linux và phần mềm nguồn mở khác, được thiết kế chủ yếu cho các thiết bị di động màn hình cảm ứng như điện thoại thông minh và máy tính bảng. Android được phát triển bởi một nhóm các nhà phát triển được gọi là Liên minh điện 35 thoại mở và được Google tài trợ thương mại. Nó được công bố vào năm 2007, với thiết bị Android thương mại đầu tiên được ra mắt vào tháng 9 năm 2008. Nó là phần mềm miễn phí và nguồn mở; mã nguồn của nó được gọi là Dự án nguồn mở Android (AOSP), được cấp phép chủ yếu theo Giấy phép Apache. Tuy nhiên, hầu hết các thiết bị Android đều được cài đặt sẵn phần mềm độc quyền bổ sung, đáng chú ý nhất là Google Mobile Services (GMS) bao gồm các ứng dụng cốt lõi như Google Chrome, nền tảng phân phối kỹ thuật số Google Play và nền tảng phát triển Dịch vụ Google Play được liên kết. Khoảng 70% điện thoại thông minh Android chạy hệ sinh thái của Google; các hệ sinh thái và dĩa Android cạnh tranh bao gồm Fire OS (được phát triển bởi Amazon.com ) hoặc LineageOS (được duy trì bởi cộng đồng). Mã nguồn đã được sử dụng để phát triển các biến thể của Android trên một loạt các thiết bị điện tử khác, chẳng hạn như máy chơi game, máy ảnh kỹ thuật số, PC và các loại khác, mỗi loại có giao diện người dùng chuyên dụng. Một số dẫn xuất nổi tiếng bao gồm Android TV cho TV và Wear OS cho thiết bị đeo, cả hai đều được phát triển bởi Google. Các gói phần mềm trên Android, sử dụng định dạng APK, thường được phân phối thông qua các cửa hàng ứng dụng độc quyền như Google Play Store hoặc Samsung Galaxy Store hoặc các nền tảng nguồn mở như Aptoide hoặc F-Droid . Android là hệ điều hành bán chạy nhất trên toàn thế giới trên điện thoại thông minh kể từ năm 2011 và trên máy tính bảng kể từ năm 2013. Tính đến tháng 5 năm 2017, nó có hơn hai tỷ người dùng hoạt động hàng tháng, cơ sở được cài đặt lớn nhất của bất kỳ hệ điều hành nào và tính đến tháng 3 năm 2020, Google Play Store có hơn 2,9 triệu ứng dụng. Phiên bản ổn định hiện tại là Android 10, được phát hành vào ngày 3 tháng 9 năm 2019. Android Inc. được thành lập tại Palo Alto, California, vào tháng 10 năm 2003 bởi Andy Rubin, Rich Miner, Nick Sears và Chris White. Rubin mô tả dự 36 án Android là "tiềm năng to lớn trong việc phát triển các thiết bị di động thông minh hơn, nhận thức rõ hơn về vị trí và sở thích của chủ sở hữu". Ý định ban đầu của công ty là phát triển một hệ điều hành tiên tiến cho máy ảnh kỹ thuật số và đây là cơ sở của nó cho các nhà đầu tư vào tháng 4 năm 2004. Công ty sau đó đã quyết định rằng thị trường máy ảnh không đủ lớn cho mục tiêu của mình và đến năm tháng sau đó, họ đã chuyển hướng nỗ lực của mình và coi Android là một hệ điều hành cầm tay sẽ cạnh tranh với Symbian và Microsoft Windows Mobile. Vào tháng 7 năm 2005, Google mua lại Android Inc. với ít nhất 50 triệu đô la. Các nhân viên chủ chốt của nó, bao gồm Rubin, Miner và White, đã tham gia Google như một phần của việc mua lại. Không có nhiều thông tin về Android bí mật vào thời điểm đó, với công ty đã cung cấp một vài chi tiết khác ngoài việc họ đang sản xuất phần mềm cho điện thoại di động. Tại Google, nhóm do Rubin dẫn đầu đã phát triển một nền tảng thiết bị di động được cung cấp bởi nhân Linux. Google đưa ra thị trường nền tảng để các nhà sản xuất thiết bị cầm tay và các tàu sân bay trên lời hứa cung cấp một hệ thống nâng cấp linh hoạt. Google đã "xếp hàng loạt các thành phần phần cứng và đối tác phần mềm và báo hiệu cho các nhà mạng rằng nó được mở cho nhiều mức độ hợp tác khác nhau". Những suy đoán về ý định của Google để thâm nhập thị trường viễn thông di động tiếp tục xây dựng thông qua December 2006. Một đầu nguyên mẫu đã có một sự tương đồng gần một BlackBerry điện thoại, không có màn hình cảm ứng và một vật lý QWERTY bàn phím, nhưng sự xuất hiện của năm 2007 của Apple iPhone đồng nghĩa với việc Android "phải quay lại bảng vẽ". Google sau đó đã thay đổi các tài liệu đặc tả Android của mình để nói rằng "Màn hình cảm ứng sẽ được hỗ trợ", mặc dù "Sản phẩm được thiết kế với sự hiện diện của các nút vật lý rời rạc như một giả định, do đó màn hình cảm ứng không thể thay thế hoàn toàn các nút vật lý". Đến năm 2008, cả Nokia và BlackBerry đều công bố 37 điện thoại thông minh dựa trên cảm ứng để cạnh tranh với iPhone 3G và cuối cùng trọng tâm của Android đã chuyển sang chỉ là màn hình cảm ứng. Điện thoại thông minh thương mại đầu tiên chạy Android là HTC Dream, còn được gọi là T-Mobile G1, được công bố vào ngày 23 tháng 9 năm 2008 Vào ngày 5 tháng 11 năm 2007, Open Handset Alliance, một tập đoàn gồm các công ty công nghệ bao gồm Google, các nhà sản xuất thiết bị như HTC, Motorola và Samsung, các nhà mạng không dây như Sprint và T-Mobile, và các nhà sản xuất chipset như Qualcomm và Texas Cụ, đã tiết lộ với mục tiêu phát triển "nền tảng thực sự mở và toàn diện đầu tiên cho thiết bị di động". Trong vòng một năm, Liên minh thiết bị cầm tay mở phải đối mặt với hai đối thủ cạnh tranh nguồn mở khác là Tổ chức Symbian và LiMo Foundation, sau này cũng phát triển một hệ điều hành di động dựa trên Linux như Google. Vào tháng 9 năm 2007, InformationWeek đã đưa tin về một nghiên cứu của Evalueserve rằng Google đã nộp một số đơn xin cấp bằng sáng chế trong lĩnh vực điện thoại di động. Kể từ năm 2008, Android đã chứng kiến nhiều bản cập nhật cải thiện hệ điều hành, bổ sung các tính năng mới và sửa lỗi trong các bản phát hành trước. Mỗi bản phát hành chính được đặt tên theo thứ tự bảng chữ cái sau một món tráng miệng hoặc đồ uống có đường, với một vài phiên bản Android đầu tiên được gọi là " Cupcake ", " Donut ", " Eclair " và " Froyo ", theo thứ tự đó. Trong thông báo về Android KitKat vào năm 2013, Google đã giải thích rằng "Vì các thiết bị này làm cho cuộc sống của chúng tôi rất ngọt ngào, mỗi phiên bản Android được đặt tên theo một món tráng miệng", mặc dù một phát ngôn viên của Google đã nói với CNNtrong một cuộc phỏng vấn rằng "Nó giống như một điều nhóm nội bộ, và chúng tôi muốn nói một chút - tôi nên nói như thế nào - một chút khó hiểu trong vấn đề, tôi sẽ nói". 38 Vào năm 2010, Google đã ra mắt loạt thiết bị Nexus của mình, một dòng sản phẩm mà Google hợp tác với các nhà sản xuất thiết bị khác nhau để sản xuất các thiết bị mới và giới thiệu các phiên bản Android mới. Sê -ri được mô tả là đã "đóng một vai trò quan trọng trong lịch sử của Android bằng cách giới thiệu các lần lặp phần mềm và tiêu chuẩn phần cứng mới trên bảng" và được biết đến với phần mềm "không phình to " với "cập nhật ... kịp thời". Tại hội nghị nhà phát triển vào tháng 5 năm 2013, Google đã công bố một phiên bản đặc biệt của Samsung Galaxy S4, trong đó, thay vì sử dụng tùy biến Android của Samsung, điện thoại đã chạy "stock Android" và được hứa sẽ nhận được cập nhật hệ thống mới nhanh chóng. Thiết bị này sẽ trở thành sự khởi đầu của chương trình phiên bản Google Play và được theo sau bởi các thiết bị khác, bao gồm phiên bản HTC One Google Play, và phiên bản Moto G Google Play. Vào năm 2015, Ars Technica đã viết rằng "Đầu tuần này, điện thoại Android phiên bản Google Play cuối cùng trong cửa hàng trực tuyến của Google đã được liệt kê là" không còn có sẵn để bán "và" Bây giờ tất cả đã biến mất, và nó trông rất giống chương trình đã kết thúc ". Từ 2008 đến 2013, Hugo Barra là người phát ngôn sản phẩm, đại diện cho Android tại các cuộc họp báo và Google I/O, hội nghị tập trung vào nhà phát triển hàng năm của Google. Anh rời Google vào tháng 8 năm 2013 để gia nhập nhà sản xuất điện thoại Trung Quốc Xiaomi. Ít hơn sáu tháng trước đó, của Google sau đó Giám đốc điều hành Larry Page tuyên bố trong một bài viết trên blog rằng Andy Rubin đã chuyển từ bộ phận Android để đưa vào dự án mới tại Google, và rằng Sundar Pichai sẽ trở thành dẫn Android mới. Bản thân Pichai cuối cùng sẽ chuyển đổi vị trí, trở thành CEO mới của Google vào tháng 8 năm 2015 sau khi tái cấu trúc công ty, làm cho Hiroshi Lockheimer trở thành người đứng đầu mới của Android. 39 Vào tháng 6 năm 2014, Google đã công bố Android One, một phiên bản Android cho phép các nhà sản xuất thiết bị dễ dàng tạo ra điện thoại chất lượng cao với chi phí thấp, được thiết kế cho người tiêu dùng ở các nước đang phát triển. Vào tháng 9, Google đã công bố bộ điện thoại Android One đầu tiên được phát hành tại Ấn Độ. Tuy nhiên, Recode đã báo cáo vào tháng 6 năm 2015 rằng dự án là "một sự thất vọng" Google đã giới thiệu điện thoại thông minh Pixel và Pixel XL vào tháng 10 năm 2016, được bán trên thị trường là điện thoại đầu tiên do Google sản xuất, và đặc trưng với các tính năng phần mềm nhất định, như Google Assistant, trước khi triển khai rộng hơn. Các điện thoại Pixel đã thay thế dòng Nexus, bằng một thế hệ điện thoại Pixel mới được ra mắt vào tháng 10 năm 2017. Vào tháng 5 năm 2019, hệ điều hành đã vướng vào cuộc chiến thương mại giữa Trung Quốc và Hoa Kỳ liên quan đến Huawei, giống như nhiều công ty công nghệ khác đã trở nên phụ thuộc vào quyền truy cập vào nền tảng Android. Vào mùa hè năm 2019, Huawei tuyên bố sẽ tạo ra một hệ điều hành thay thế cho Android được gọi là Harmony OS, và đã nộp đơn xin quyền sở hữu trí tuệ trên các thị trường lớn trên toàn cầu. Huawei hiện không có bất kỳ kế hoạch nào để thay thế Android trong tương lai gần, vì Harmony OS được thiết kế cho internet mọi thứ thiết bị, thay vì cho điện thoại thông minh. Vào ngày 22 tháng 8 năm 2019, Android "Q" sẽ chính thức được gắn nhãn là Android 10, chấm dứt thực tiễn lịch sử đặt tên các phiên bản chính sau các món tráng miệng. Google tuy